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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
#include <iostream> #include <bitset> using namespace std; // Find number of bits needed to be flipped to convert x to y int findBits(int x, int y) { // take XOR of x and y and store in n int n = x ^ y; // Using Brian Kernighan's algorithm to count set bits // count stores the total bits set in n int count = 0; for (; n; count++) n = n & (n - 1); // clear the least significant bit set return count; } // main function int main() { int x = 65; int y = 80; cout << x << " in binary is " << bitset<8>(x) << endl; cout << y << " in binary is " << bitset<8>(y) << endl; cout << "\nThe number of bits flipped is " << findBits(x, y); return 0; } |

`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++

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
#include <iostream> using namespace std; // return true if binary representation of n is a palindrome bool isPalindrome(unsigned n) { // rev stores reverse of binary representation of n unsigned rev = 0; // do till all bits of n are processed unsigned k = n; while (k) { // add rightmost bit to rev rev = (rev << 1) | (k & 1); k = k >> 1; // drop last bit } // return true if reverse(n) is same as n return n == rev; } // main function int main() { int n = 9; // 1001 if (isPalindrome(n)) cout << n << " is Palindrome"; else cout << n << " is not a Palindrome"; return 0; } |

`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

Can someone please explain how the binary number is being reversed.

————————————————————

————————————————————

Output if n=9

k val is 00000100

rev val is 00000001

k val is 00000010

rev val is 00000010

k val is 00000001

rev val is 00000100

k val is 00000000

rev val is 00001001

9 is Palindrome

————————————————————

As far as I know, only first expression is executed if it is true for "|" condition statement. So, here rev<<1 will be false only for first case but not for others. Therefore how does rev get 1 in the end for last condition because (k&1) won't be executed. Only left shift will be executed right?