Vamsi Pavan’s Place

1. Reverse the bits of an unsigned integer.

ANS.

    #define reverse(x)
              (x=x>>16|(0×0000ffff&x)<<16,
               x=(0xff00ff00&x)>>8|(0×00ff00ff&x)<<8,
               x=(0xf0f0f0f0&x)>>4|(0×0f0f0f0f&x)<<4,
               x=(0xcccccccc&x)>>2|(0×33333333&x)<<2,
               x=(0xaaaaaaaa&x)>>1|(0×55555555&x)<<1)

*2. Compute the number of ones in an unsigned integer.

ANS.

   #define count_ones(x)
              (x=(0xaaaaaaaa&x)>>1+(0×55555555&x),
               x=(0xcccccccc&x)>>2+(0×33333333&x),
               x=(0xf0f0f0f0&x)>>4+(0×0f0f0f0f&x),
               x=(0xff00ff00&x)>>8+(0×00ff00ff&x),
               x=x>>16+(0×0000ffff&x))

3. Compute the discrete log of an unsigned integer.

ANS.

#define discrete_log(h)
 (h=(h>>1)|(h>>2),
 h|=(h>>2),
 h|=(h>>4),
 h|=(h>>8),
 h|=(h>>16),
 h=(0xaaaaaaaa&h)>>1+(0×55555555&h),
 h=(0xcccccccc&h)>>2+(0×33333333&h),
 h=(0xf0f0f0f0&h)>>4+(0×0f0f0f0f&h),
 h=(0xff00ff00&h)>>8+(0×00ff00ff&h),
 h=(h>>16)+(0×0000ffff&h))

If I understand it right, log2(2) =1, log2(3)=1, log2(4)=2….. But this macro does not work out log2(0) which does not exist! How do you think it should be handled?

*4. How do we test most simply if an unsigned integer is a power of two?
ANS.
#define power_of_two(x) \ ((x)&&(~(x&(x-1))))

5. Set the highest significant bit of an unsigned integer to zero.

ANS. (from Denis Zabavchik) Set the highest significant bit of an unsigned integer to zero
#define zero_most_significant(h) \
(h&=(h>>1)|(h>>2), \
h|=(h>>2), \
h|=(h>>4), \
h|=(h>>8), \
h|=(h>>16))

6. Let f(k) = y where k is the y-th number in the increasing sequence of non-negative integers with the same number of ones in its binary representation as y, e.g. f(0) = 1, f(1) = 1, f(2) = 2, f(3) = 1, f(4) = 3, f(5) = 2, f(6) = 3 and so on. Given k >= 0, compute f(k).