Bit Manipulation
Reverse the bits of an unsigned integer.
http://halcyon.usc.edu/~kiran/msqs.html
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)
int cnt=0,num=0,temp=0,res=0;
while(cnt<32) // here i consider size of integer to be 32-bit
{
temp=num & 1; // num contains the value of integer
res=res | temp;
num=num>>1;
res=res<<1;
cnt++;
}
Bitset
express a integer as a bit in a 32 bit DWORD. the numbers are from 1 ~10000000.
These functions use the constants to set, clear and test the value of a bit:
#define BITSPERWORD 32 #define SHIFT 5 #define MASK 0x1F #define N 10000000 int a[1 + N/BITSPERWORD]; void set(int i) { a[i>>SHIFT] |= (1<<(i & MASK)); } // i >> SHIFT == i / 32 ; i & MASK == i % 32; void clr(int i) { a[i>>SHIFT] &= ~(1<<(i & MASK)); } int test(int i){ return a[i>>SHIFT] & (1<<(i & MASK)); }
count bits in an 32 bit integer
int NumOnesInBinary(int number)
{
int numOnes = 0;
while (number) {
if (number & 1)
numOnes++;
number = number >> 1;
}
return numOnes;
}
int NumOnesInBinary(int number)
{
int numOnes = 0;
while (number) {
number = number & (number - 1);
numOnes++;
}
return numOnes;
}
How to reverse the odd bits of an integer?
XOR each of its 4 hex parts with 0101.