This
page lists commonly used bit operations logic and in some cases, implementation
in C.
BASICS of Bit operations
<Please note if you are
comfortable with basics, move to next section.>
Whenever solving any bit operations, try to do it on a smaller scale.
For example, lets say the task is to extract odd bits,
- Prepare the mask for 1 Byte=0101010101 =0x55 will give odd
bits
- Solve for smaller number, try to prepare test number in
binary num = 0000 1101
- To extracet, if we just to bitwise & of number with
mask, (0000 1101) & (0x01010101), we get all odd bits.
- Extend for larger number say integer, num&0x55555555
will give all odd bits.
Kick-Starting on Bit Ops
This section talks about basic problems on bit operations, like divisibility of a number, how multiplication takes place for simple(power of 2) and mixed numbers (any other number)
Multiplication by 2x :
Example: Multiple 11 by 2
(11) = 0000 1011
*2=22 = 0001 0110
See any connection? All bits are
shifted to left. So solution is, number<<1 to multiple by 2.
Lets extend this to multiply by 4
Example: Multiple 11 by 2
(11) = 0000 1011
*4=44 = 0010 1100
Similar connection, all bits shifted
twice. number<<2 to multiple by 4.
We can reverse logic (i.e. shift right) to divide by 2 or 4 or any other power of 2.
This way, never need to remember how to multiply or divide number by any power of 2.
Exercise: How to find by how much to shift to multiply/divide a number of a power of 2 number.
Next, How to multiply/divide a number by a mixed number (not power of 2)?
Multiplication by 3
3 = 0000 0011 => 2+1
num*3 = num*2 + num*1
Multiplication by 27
27=0001 1011 => 16+8+2+1
num*27 = num*16 + num*8 + num*2 + num*1
Multiplication by 5.25
5.5 = 4 + 1 + 0.25 = 4 + 1 + (1/4)
so, answer can be obtained as,
n>>2 + n + n<<2 [Recall: Right shift twice is divide by 4,
and left shift twice is multiple by 4.
Idea: Using bitwise OR (|) can be equivalent to addition.
Say, 7+10 = (0000 0111) + (0000 1010) =
(0001 0001) = 17
Logic: And(&) number with all set
bits in given multiplier, and Or(|) all these results.
Exercise: Try to convert this into C code and see if this logic works?
Next, Check if a number if power of two?
Let us take three numbers, 7, 8 and 18.
7 = 0000 0111
8 = 0000 1000 => If we &
this with 7, we get all 0s. And this is power of two number. Any connections or
just coincidence?
17 = 0001 0001
18 = 0001 0010 => If we & this
with 17, we dont get all 0s, and this is not power of two number.
Lets take some more,
15 = 0000 1111
16 = 0001 0000 => If we & this
with 15, we get all 0s and this is power of two.
This way we reach, if we do "n&(n-1)" and result is all zero, the number if power of two.
Any corner cases? What about 0?
So, for a number n to be power of 2,
this expression should evaluate to 1, n && ! n&(n-1)
Check if given number is divisible by 9
Explained Here:
if(num==0 || num==9) return 1;
else if(num<9) return 0;
return IsDivBy9( (int)(n>>3) - (int)(n&7) );
Next, What is parity of a number?
Parity of a number is calculated based
on whether number of set bits are even or odd.
To count set bits in a number, pseudo code can look like
while(n) { n&=(n-1); cnt++; }
And then its easy to check if cnt is
odd or even. Easy, isnt' it?
Recursive count set bits
uint cnt_set_bits(uint num)
{
if(num<=0) return 0;
return (num%2 == 0 ? 0 : 1) +
cnt_set_bits(num/2);
}
Generate mask where bit m is unset, rest
bits are set
~(1 << (m - 1)) //very
useful
Exercise: Turn m-th bit on: (1<<m) &num //is this right?
Or, this one? (1<<m) | num
Check if given bit is set?
int IsBitSet(uint num, uint bit) //bit:0-31
{ return (num & (1<<(bit)) ) ? 1 : 0; }
Next, Find what is rightmost set bit of a number?
Lets us try to solve with a number, say
7.
Disclaimer: This solution is not intuitive unless you have seen it
before.
7 = 0000 0111 => bit 0
Imaging how -7 is stored in machine? Heard of 2's complement scheme.. yes that's right.
2's complement: flip all bits and add
1.
So, -7 = 1111 1000 +1 = 1111 1001
Note, since this is negative number,
most machine will have sign bit extension, and if we extend this representation
to 32 bit scheme, it becomes, 1111 1111 1111 1111 1111 1111 1111 1001
Lets & these two, 7 + (-7) = (0000 0111) & (1111 1001) = (0000 0001) , and take log of this,
log (base2) 1 = 0, so bit 0 is
rightmost set bit here.
Let us take one more number, say 18.
18 = 0001 0010
-18 = (1110 1101) +1 = (1110 1110)
18 & -18 = (0001 0010) & (1110
1110) = (0000 0010) =2. Take log(base2) 2 = 1
So, 1st bit is rightmost set bits.
Please post in comment if you see this rule getting violated.
Turn off right most set bit
What happens if we & a number with
its predecessor?
Let us take number 5,
5 = (0000 0101), we wnat result as
(0000 0100)
& with 4 (=0000 0100) => (0000
0100). Looks like result isn't it?
Not convinced, take another example,
16=(0001 0000)
&with 15(=0000 1111) = (0000 0000)
Looks like what we were trying to do.
How to reverse all bits in a number?
Idea Exploration?
Say a number 5 (=0000 0110), its
reverse is (0110 0000). [Only 8-bit representation for examples]
Lets say, n is input number, rev is reversed number.
nbits=sizeof(n)*sizeof(char) -1 //32
bits
1. start with reverse equal to n, and
shift n right once: rev=n; n>>=1;
rev = (0000 0110),
n>>=1: n=(0000 0011)
2. while(n) { rev<<=1;
rev|=n&1; n>>=1; nbits--; }
Loop1: rev<<=1:
rev=(0000 1100), rev|=n&1: rev=(0000 1101) n>>=1: n=(0000 0001)
Loop2: rev<<=1:
rev=(0001 1010), rev|=n&1: rev=(0001 1011) n>>=1: n=(0000 0000)
Loop break. we have
shifted twice, so remaining 30 left shifts
3. rev<<=nbits;
Disclaimer: Another non intuitive
solution. But once you see it, you cant go back to naive approach.
Next, You have two numbers, want to calculate how many bits to flip so that first number becomes second
A= 7 = (0000 0111)
B= 70= (0100 0110)
To convert A to be, I would need to
swap, 2 bits.
XOR operation to the rescue, What is
XOR of A and B?
A^B = (0100 0001), and now count set
bits in A^B to get answer.
Rotate Bits of given number by given rotation d
Relevant questions,
Which side, left or right? Looks
simple, isn't it?
n<<d, or n>>d.
What is the catch here? Does left or right shift make any difference?
The trick is to ensure that falling
bits are put back to right or left and not simply discarded.
How to do? First extract the bits which
are going to be fallen, move them to opposite direction than the rotation is
requested and then | with shifted number.
To extract bits going to be fallen, the mask should be (INT_BITS-d). INT_BITS= sizeof(n)*sizeof(char)-1
Now, we can frame full solution,
leftRoation(n, d) { return (n<<d) | (n>> (INT_BITS-d)) }
rightRotation(n,d){ return (n>>d)
| (n<<(INT_BITS-d)) }
Add two numbers using bit operations
Lets try few small additions of 1 bit:
(0+0) = 0, carry=0
(0+1) = 1, carry=0
(1+1) = 0, carry 1
Concept: sum=a^b(xor), carry=a&b
Idea:
We can use one variable as sum, shift another while adding.
int add(int a, int b) {int carry; while(b) { carry=a&b; a=a^b; b=carry<<1; } return a; }
int AddRecursive(int
x, int y)
{
if (y==0) return x;
else return AddRecursive(x^y ,
(x&y)<<1 );
}
To understand flow, lets take x=0xF11,
y=0xFFF.
x=f111, y=fff, calling
AddRecursive(x^y=feee, (x&y)<<1=222)
x=feee, y=222, calling
AddRecursive(x^y=fccc, (x&y)<<1=444)
x=fccc, y=444, calling
AddRecursive(x^y=f888, (x&y)<<1=888)
x=f888, y=888, calling
AddRecursive(x^y=f000, (x&y)<<1=1110)
x=f000, y=1110, calling
AddRecursive(x^y=e110, (x&y)<<1=2000)
x=e110, y=2000, calling
AddRecursive(x^y=c110, (x&y)<<1=4000)
x=c110, y=4000, calling AddRecursive(x^y=8110,
(x&y)<<1=8000)
x=8110, y=8000, calling
AddRecursive(x^y=110, (x&y)<<1=10000)
x=110, y=10000, calling
AddRecursive(x^y=10110, (x&y)<<1=0)
x=10110
[All hex values] Add 0xF111 and 0xFFF:
10110
Subtract two numbers with bit operations
while(b) { int borrow = (~a)&b; a=a^b; b=borrow>>1 }
int subtrace_recursive(int a, int b)
{ if(b==0) return a;
return subtract(a^b, (~a&b)<<1 );
}
Swap n bits starting at given positions
Lets say, we need to swap n=2 bits,
starting pos1=1 and pos2=5
binary num= 1010 1110
result = 0111 0011
mask = (1U << n) -1 =
(1U<<2)-1 = (100)-1 = (11)
rightpart = (num>>pos1) & mask; (11)
leftpart = (num>>pos2)
& mask (01)
xor=rightpart ^ leftpart
(10)
xor= (xor<<pos1) |
(xor<<pos2) (0100 0100)
result=num ^ xor
(0110 0010) = answer
Find if given numbers are of opposite sign
return ( (a^b) >> 32 )
return ( (a^b) < 0 )
Find position of lone set bit
if ( (n &&
!(n&(n-1))) == 0) it has more than 1 setbits
return Log2n(n)+1 OR
while(n){n>>=1; ++cnt;}
Check if given number is sparse
In sparse number, no two or more consecutive bits are set.
Idea: Do & of number with its right shifted number.
How to calculate XOR of two numbers without operator
unsigned int XOR(unsigned int
a, unsigned int b)
return (a | b) & (~b | ~a);
Verify if binary representation in palindrome
left=0, right=sizeof(int)*8 -1;
while(left<right) { if ((IsBitSet(num, left) != IsBitSet(num, right)) return 0;
left++; right++; }
return 1;
while(left<right) { if ((IsBitSet(num, left) != IsBitSet(num, right)) return 0;
left++; right++; }
return 1;
Reference
No comments:
Post a Comment