Bit Hacks – Part 6 (Random Problems)

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

 

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.

C++

Download   Run Code

Output:

65 in binary is 01000001
80 in binary is 01010000

The number of bits flipped is 2

 

2. 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++

Download   Run Code

Output:

9 is Palindrome

 
Read More –

Bit Hacks – Part 1 (Basic)
Bit Hacks – Part 2 (Playing with k’th bit)
Bit Hacks – Part 3 (Playing with rightmost set bit of a number)
Bit Hacks – Part 4 (Playing with letters of English alphabet)
Bit Hacks – Part 5 (Find absolute value of an integer without branching)

Conditionally negate a value without branching
Find XOR of two numbers without using XOR operator
Find if adjacent bits are 1 in binary representation of a number

 
Suggested Read: https://graphics.stanford.edu/~seander/bithacks.html
 

Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 





Leave a Reply

Notify of
avatar
wpDiscuz