Bit manipulation problems | Hello World
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.
Read full article from Bit manipulation problems | Hello World
