Bit manipulation problems

This kind of problem is not hard but just get familiar with the and or and xor operations.

1. Given a (decimal – e.g. 3.72) number that is passed in as a string, print the binary representation. If the number can not be represented accurately in binary, print “ERROR”
The integer part is easy, how about the decimal part.
the decimal part follows the same rule as the integer part, D = d1*(1/2^1) + d2(1/2^2) + d3(1/2^3) + …
So for a decimal number say D = 0.14, we multiple it by two and check if result is greater than 1. It is the same result as shifting the binary representation left by 1 and check if it gets larger than 1. and if so, the next bit is 1. We do this until we get decimal number to 0.

2. Given an integer, print the next smallest and next largest number that have the same number of 1 bits in their binary representation.
We know that at some digit d, we flip 1 to 0 will decrease the number by 2^d and flip 0 to 1 will increase the number by 2^d. If we want to keep the same number of 1s in the number, we have to flip 1 bit from 1 to 0 and 1 bit from 0 to 1. So
for the next smallest number: we need a lower bit flip to 1 and a higher bit flip to 0. So we have to pass 1 and then find the next 0 to flip, so
1. we search from the right, after we passed a 1, we turn on the next 0 this makes sure we have a larger number than the input, then we do what ever we can to decrease the number on the right of this bit.
2. Then we turn off the 1 next to it, so we remove the largest number of the right of the bit we turned on in step 1.
3. We move the rest of the 1 s to the far right so that the number gets as small as possible.

In the same way, to find the next largest number, we need to flip a lower bit from 1 to 0 and a higher bit from 0 to 1. the idea is the same.

3.Explain what the following code does: ((n & (n-1)) == 0).
First lets look at what if A&B == 0 means, it means A and B has one 0 or all the bits between A and B are different.
So if n and n-1 has not bits in common, then n must be 1 with a serials of 0s following it. which means n is 2^n or n = 1 or n = 0;

4.Write a function to determine the number of bits required to convert integer A to integer B.
The solution is actually quite straightforward, find the bits difference between A and B, so xor each bit and count the number of difference.

5.Write a program to swap odd and even bits in an integer with as few instructions as possible (e.g., bit 0 and bit 1 are swapped, bit 2 and bit 3 are swapped, etc).
Instead of doing the swap, we use two mask 0xAAA… and 0x555… to mask out the odd and even bits, shift the number and then put them together.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s