a little fun with bits

you all have seen bits while reading something related to computers , specially in fields like computer architecture, etc but bits can serve us a great comfort in coding or solving medium or tough problems in computer languages like c or c++. so here we go....
suppose A=1100 ,B= 1010 then
A|B= 1110 (OR)
A&B= 1000 (AND)
A^B= 0110 (XOR- if there are odd number of 1s then 1 else 0)

x<<y means left shifting of bits of x by y or multiplication of x with 2^y
x>>y means right shifting of bits of x by y or division of x with 2^y

the most important use of shifting is to access a particular bit, for example 1<<x denotes x bit from the right set (1) and all other not set (0)



following are some operations on sets in terms of bits, (A=1100 B=1010, last item is absent in both , second last is present in B but absent in A and so on)

Set Union- A|B
Set Intersection- A&B
Set Negation(0 to 1 or 1 to 0)- ALL_BITS^A (where ALL_BITS is number with same number of bits as in A but all set (1) )



if we want to substract two numbers in  binary form then we instead perform a add operation ..... this is shown below
if A= 10101 and B= 11000 and we want to perform A-B then we would perform A+(-B), now in order to convert B to -B we have to take its two's complement as follows
B= 11000
B's one's complement= ~B= 00111
B's two's complement= ~B+1= 00111+00001= 01000
now simply A-B= A+(-B)= 10101+01000= 11101


Now suppose we want to find out the lowest bit in x which is set (1),,, by lowest we mean first encountered from the right hand side....
thus if x= 10100 and -1= 1111111 (in -1 all the bits are set, always)
x-1= x+(-1)= 10011
~(x-1)= 01100
x & ~(x-1)= 00100

thus to find the lowest bit which is set(1) perform x & ~(x-1)


to reverse the bits of an integer something not so simple has to performed...

x = ((x & 0xaaaaaaaa) >> 1) | ((x & 0x55555555) << 1);
x = ((x & 0xcccccccc) >> 2) | ((x & 0x33333333) << 2);
x = ((x & 0xf0f0f0f0) >> 4) | ((x & 0x0f0f0f0f) << 4);
x = ((x & 0xff00ff00) >> 8) | ((x & 0x00ff00ff) << 8);
x = ((x & 0xffff0000) >> 16) | ((x & 0x0000ffff) << 16);


bye bye :)