Binary based problems

Find the number of set bits in the binary equivalent of a decimal number. The solution is required to be O(1) in both time and space. here is a slick solution. Although it is claimed here that it is nearly O(1), I’m not sure the judges would have accepted it.

For any unsigned number b, n is the number of signed bits, and n is calculated as follows:

for(n=0; b; b >>= 1)
if (b & 1) n++;

Un more. From an infinte bit stream, determine whether the decimal equivalent of the binary obtained so far is divisible by three.

Sum the even and odd bits separately. If their difference is divisible by three, so is the number. You can obtain the result by considering the number is represented as Summatuion over(3-1)^n instead of the usual Sum over 2^n, and then expanding using binomial expansion.

Too bad, this didn’t strike me during the event. More problems will be posted. You are free to request or even send interesting Qs to me.

Advertisements

2 thoughts on “Binary based problems

  1. The way you posted to count the no of bits is O(b) where is b is the no of bits in the number.

    There is another way to get it in O(k) where k is the number of 1s in the number šŸ™‚ Try it šŸ™‚

  2. Thanks a lot for bringing to my notice that there is a O(k) solution. I didn’t think there was something special about the algorithm I has posted previously, however, here’s the better algorithm

    while(n)
    n = n &( n-1 ), count++;

    It works by setting the rightmost bit to zero.
    here‘s a good reference on set-bit counting.

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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