# Bit Hacks – Part 6 (Random Problems)

In this post, we will discuss few unrelated problems that can be solved using bit manipulation hacks.

Below Problems are covered in this post –

Problem 1. Find number of bits needed to be flipped to convert given integer to another

The idea is to take XOR of given two integers. After calculating the XOR, the problem will reduces to counting set bits in the XOR output. We have already discussed how to count set bits in an integer in below post –

Brian Kernighan’s Algorithm to count set bits in an integer

C++ implementation –

Output:

65 in binary is 01000001
80 in binary is 01010000

The number of bits flipped is 2

Problem 2. Conditionally negate a value without branching

The expression ((flag^(flag-1))*n) negate n when the flag is false and the expression
((n^-flag)+flag) negate n when the flag is true.

How does it work?

For (flag ^ (flag – 1)) * n

if flag = 0, (0 ^ (-1)) * n = -n
if flag = 1, (1 ^ (0)) * n = n

For (n ^ -flag) + flag

if flag = 0, (n ^ 0) + 0 = n
if flag = 1, (n ^ -1) + 1 = ~n + 1 = -n (2’s complement notation)

C++ implementation –

Output:

Don’t Negate 2
Negate -2

Problem 3. Find XOR of two numbers without using XOR operator

Naive Solution would be to consider every bit present in both numbers one by one (either from left or right) and compare them. If the current bit is same in both numbers (i.e. both are 0 or both are 1), we set it as 0 else we set it as 1 and move to next pair of bits until all bits are processed.

The expression ((x | y) – (x & y)) is equivalent to x ^ y (finding XOR of two numbers x and y). XOR works by setting the bits which are set in either of one of the given numbers (0 ^ 1 = 1,
1 ^ 0 = 1)
and finally taking out the common bits with are present in both (1 ^ 1 = 0).
For example,

01000001   |                 (x = 65)
01010000                     (y = 80)
~~~~~~~~
01010001                     (x | y)

01000001   &                 (x = 65)
01010000                     (y = 80)
~~~~~~~~
01000000                     (x & y)

Now the result x ^ y would be (x | y) – (x & y) = (01010001 – 01000000) = 00010001

C++ implementation –

Output:

First number in binary is 01000001
Second number in binary is 01010000

XOR is 00010001

Problem 4. Find if adjacent bits are 1 in binary representation of a number

Naive Solution would be to consider every bit present in the number one by one and compare it with its previous bit. If the current bit is same as previous bit, then we have found a pair whose adjacent bits are 1.

The expression (n & (n << 1) or (n & (n >> 1) will return true if n contains any pair whose adjacent bits are 1. For example,

00101101   &                 (n)
01011010                     left shift n by 1
~~~~~~~~
00001000                     (n & (n << 1))

C++ implementation –

Output:

67 in binary is 01000011
Adjacent pair of set bits found

Problem 5. Check if binary representation of a number is palindrome or not

For example, 101, 11, 11011, 1001001 are palindromes. 100, 110, 1011, etc are not palindromes.

Well, there is no one-liner trick to solve this one. 😛

The idea is to construct reverse of binary representation of n and return true if it is same as n.

C++ implementation –

Output:

9 is Palindrome