I will be talking here, about some of the coolest language agnostic bit hacks. Below diagram, gives brief idea about the relative positions of bits in a 1 byte number. Right most bit, 0th is LSB and left most bit, 7th bit is MSB.
Below table, will be handy to understand the behavior of SHIFT operators. It is used to manipulate a bit a particular position like 3rd, 7th etc. LSB is 0th bit and MSB is 7-th bit (as shown in above diagram as well).
00000001 (1 in binary)
& 11111110 ( ~(1<<0) )
------------
00000000
01001001 (73 in binary)
& 11110111 ( ~(1<<4) )
------------
01000001
General formula for unsetting n-th bit of a number X
Recall that, XOR-ing a bit with 1 will turn it to 0 if it's already 1 and vice-versa.
01001001 (73 in binary)
^ 00001000 ( 1<<3)
------------
01000001
It can be generalized as:
X = X ^ (1<< n)
---
do post your inputs/feedback.
keep coding !!!
Bit operators
Just as a re-cap, let's start with the list of bit operators. I have discussed about them, here. I have not included unsigned right shift operator, >>> in below list, as it's specific only to Java.
& - Bitwise ANDAbove operators are mostly used for bit level manipulation.
| - Bitwise OR
^ - Bitwise XOR
~ - Bitwise NOT
>> - Bitwise SHIFT LEFT
<< - Bitwise SHIFT RIGHT
Below table, will be handy to understand the behavior of SHIFT operators. It is used to manipulate a bit a particular position like 3rd, 7th etc. LSB is 0th bit and MSB is 7-th bit (as shown in above diagram as well).
Note - index starts from 0.1<<0 or 1 - 00000001
1<<1 - 00000010
1<<2 - 00000100
1<<3 - 00001000
1<<4 - 00010000
1<<5 - 00100000
1<<6 - 01000000
1<<7 - 10000000
Bit Hacks
Here, we will always consider 8 bit (1 byte) signed numbers to explain all hacks. The same approach can be used for signed number of any size (like 16, 32 bits etc ).
00000000 (0 in binary)
| 00000001 ( 1 or 1 << 0)
------------
00000001
01001001 (73 in binary)
| 00001000 ( 1<<3)
------------
01001001
General formula for setting n-th bit of a number X
#1: Set bit at a position
Setting a bit means, updating its
value to 1 (irrespective of the current value). OR-ing a bit with 1 sets
the bit ( & OR-ing a bit with 0 leaves it unchanged).
00000000 (0 in binary)
| 00000001 ( 1 or 1 << 0)
------------
00000001
01001001 (73 in binary)
| 00001000 ( 1<<3)
------------
01001001
General formula for setting n-th bit of a number X
X = X | 1 << n
#2: Unset bit at a position
To unset a bit, we need to AND it with 0. But the tricky part is that, other bits should be 1 so that the only the target bit gets unset.
00000001 = 1
11111110 = ~1
& 11111110 ( ~(1<<0) )
------------
00000000
01001001 (73 in binary)
& 11110111 ( ~(1<<4) )
------------
01000001
General formula for unsetting n-th bit of a number X
X = X & ~(1<< n)
#3: Toggle a bit
Toggling a bit means flipping it; i.e. make it 1 if it is 0 and 0 if it is 1. So we need to use something which turns 0 to 1 and 1 to 0.
Test if the bit is set.
- If set, AND it with 0 (to make it 0)
- if not set, OR it with 1 (to make it 1)
Let's take a case where we want to toggle the MSB of a 8 bit variable, X whose value is -1.
Above approach works, but it require multiple operations to toggle a bit. Can it be done using a single step? YES!//n = 7if(X & (1<<n) == 0){//nth-bit is setX = X & ( 1<< n)}else{//nth-bit is not setX= X | (1<<n)}
Recall that, XOR-ing a bit with 1 will turn it to 0 if it's already 1 and vice-versa.
01001001 (73 in binary)
^ 00001000 ( 1<<3)
------------
01000001
It can be generalized as:
X = X ^ (1<< n)
---
do post your inputs/feedback.
keep coding !!!
No comments:
Post a Comment