1. Reverse the bits of an unsigned integer.
ANS.
#define reverse(x)
(x=x>>16|(0x0000ffff&x)<<16,
x=(0xff00ff00&x)>>8|(0x00ff00ff&x)<<8,
x=(0xf0f0f0f0&x)>>4|(0x0f0f0f0f&x)<<4,
x=(0xcccccccc&x)>>2|(0x33333333&x)<<2,
x=(0xaaaaaaaa&x)>>1|(0x55555555&x)<<1)
*2. Compute the number of ones in an unsigned integer.
ANS.
#define count_ones(x)
(x=(0xaaaaaaaa&x)>>1+(0x55555555&x),
x=(0xcccccccc&x)>>2+(0x33333333&x),
x=(0xf0f0f0f0&x)>>4+(0x0f0f0f0f&x),
x=(0xff00ff00&x)>>8+(0x00ff00ff&x),
x=x>>16+(0x0000ffff&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+(0x55555555&h), h=(0xcccccccc&h)>>2+(0x33333333&h), h=(0xf0f0f0f0&h)>>4+(0x0f0f0f0f&h), h=(0xff00ff00&h)>>8+(0x00ff00ff&h), h=(h>>16)+(0x0000ffff&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).