Bit-wise operations tactics.
A bit is a basic unit of information in the computer system and digital communications and It represents a logical state of one of two values. i.e (“1 or 0”/ ”true or false” )
This is a collection of some tricks that I have come across while dealing with Arduino, Raspberry-pi, esp8266, and ROS (Robot Operating System) projects. I have enormously used bitwise operators to save memory and network calls. From that experience here I have collected some tips and tricks that I felt were worth sharing.
Here are the bitwise notations and their meanings.
~— Bitwise NOT&— Bitwise AND|— Bitwise OR^— Bitwise XOR<<— Left Shift>>— Sign-Propagating Right Shift>>>— Zero-Fill Right Shift
Manipulating bit.
Turn off Rightmost 1-bit in the word. e.g ( 01001000 => 01000000).
Steps:
- Subtract 1 from the original word. (0b01001000 -1 = 0b1000111)
- use the above result and do ‘&’ operation with the original word.
( 0b01001000 & 0b1000111 = 0b01000000)
3. Result will show the rightmost 1-bit is set and 0.
In [1]: x = 0b10100100
In [2]: x = x & (x-1)
In [3]: bin(x)
Out[3]: ‘0b10100000’Turn On Rightmost 0-bit in a word e.g. (10100111 => 10101111).
Steps:
- Add 1 to the original word (0b10100100+1 = 0b10101000)
- use above output and do ‘|’ (or) operation with the original word.
In [4]: x = 0b10100111
In [5]: x = x |(x+1)
In [6]: bin(x)
Out[6]: '0b101001111'Turn Off trailing 1’s in a word e.g. (10100111 => 10100000)
Steps:
- Add 1 to the original word (0b10100111+1 = 0b10101000)
- use the above output and do ‘&’ (and) operation with the original word.
In [7]: x = 0b10100111
In [8]: x = x & (x+1)
In [9]: bin(x)
Out[9]: '0b10100000'Turn On trailing 0’s in a word e.g. (10101000 => 10101111)
Steps:
- Subtract 1 from the original Word (0b10101000–1 = 0b10100111).
- use above output and do ‘|’ (or) operation with original word.
In [13]: x = 0b10101000
In [14]: x = x | (x-1)
In [15]: bin(x)
Out[15]: '0b10101111'Turn On/Off bit on N’th position in the word.
- Turn ‘off’ a bit on n’th position in the world.
In [1]: word = 0b11111111 # this is a original wordIn [3]: position = 2 # On this position bit will set as 'Off' or 0.In [4]: mask = 1 << position # Bit mask of the position.In [5]: bin(mask)
Out[5]: '0b100'In [6]: bin(word & ~mask) # and operation of word with the not(mask). This will set the position bit as 'off' in a word.
Out[6]: '0b11111011'
2. Turn ‘On’ a bit on n’th position in the word.
In [1]: word = 0b11111011 # This is a original word.In [2]: position = 2 # This s position of bit that we wanted to set as 'On'In [3]: mask = 1 << position # Bit mask of the position.In [4]: bin(mask)
Out[4]: '0b100'In [5]: word = word | mask # OR operation between original word and bit mask. This will set the bit as 'On' on that particular position.In [6]: bin(word)
Out[6]: '0b11111111'
Bit counting on/off bits in a word.
Counting all ‘On’/1-bits in a word. Loop through all bits in an integer, check if a bit is set (To check bit is ‘On’ or ‘off’ method is mention in the above section.) and if it then increments the set bit count. See below program.
In [16]: def countOnBits(n):
...: count = 0
...: while(n):
...: count += n & 1
...: n >>= 1
...: return count
...:In [17]: word = 0b11010011
In [18]: print(countOnBits(word))5
Counting All Off 0-bit in a word. The same method as the above only change is increment counter when a bit is found as ‘0’.
In [22]: def countOffBits(n):
...: count = 0
...: while(n):
...: count += not(n & 1)
...: n >>= 1
...: return count
...:In [23]: word = 0b11010011
In [24]: print(countOffBits(word))3
Toggle Bit
make bit 0 to 1 and 1 to 0 on specific position.
With the help of XOR operation we can toggle a bit 0 → 1 or 1 → 0.
Steps:
- First create bit mask for that particular position.
- Do XOR operation between word and mask.
In [20]: def toggleBit(word, position):
...: return (word ^ (1 << (position-1)))
...:In [21]: word=0b11111111In [22]: position = 2In [25]: word = toggleBit(word, position) # Toggling 1 -> 0 on the specified position in a word.In [26]: bin(word)
Out[26]: '0b11111101' # 2nd position is changed to '0'.In [27]: word = toggleBit(word, position) # again toggling 0 -> 1 on the specified position in a word.In [28]: bin(word)
Out[28]: '0b11111111' # 2nd position is changed to '1'
Bit Masking application.
In the above few tricks, there is a ‘mask’ word that has appeared multiple times, so what is it? and what is the use of that? Let’s see more about bit masking.
It is a Binary pattern used to modify another binary pattern using bitwise operation (&,|,~,^)
As we know In a binary there are two states of bit 0 and 1 or “On” and “Off”. And 1-byte contains 8-bits. We can use this 1 byte to maintain a state of 8 different components e.g. let consider there are 8 LED’s you want to control in your program and you have planned to maintain a state of LED in different variable but it will cost you for the space. Instead of that, you can use 1-byte to maintain a state of 8 different LED’s and by using bit-mask and bitwise operation you can change the state of individual LED’s. The following examples will help you to understand Bit-mask.
Let consider initially all LED’s are in the “ON” state and this will represent in byte by setting all bits to 1 like 0B11111111 (0xff in hex and 255 in decimal). Same way if all LED’s are off state then all bits in a byte are set to 0.
And now you want to change some LED’s state so how we can do that? Let’s see the below method.
Here I am creating mask for each LED.
LED1 = 0b00000001
LED2 = 0b00000010
LED3 = 0b00000100
LED4 = 0b00001000
LED5 = 0b00010000
LED6 = 0b00100000
LED7 = 0b01000000
LED8 = 0b10000000And the state of all LED’s get stored in below variable. Initially I am setting all LED’s to ‘On’ Position.
STATE = 0b11111111Now suppose you want to turn off the 3rd LED for that we need to change the 3rd position bit to ‘0’. That process I already mentioned in the “Turn On/Off bit on N’th position in the word.” section. Likewise, we can toggle/set/unset the value of a bit using its mask value.
STATE &= ~LED3; '0b11111011' This will help in case of network calls e.g. Suppose your LED’s are in a remote position and you need to make a network call to maintain their state then by using one network call you can manage a state of 8 LED’s. :-)
Swap two integer values using bitwise Operator.
To swap two integer using bitwise operator only 3 XOR operations are required as follow.
- num1 = 0b00000001 (1 in decimal) ; num2 = 0b00000011 = 3
- num1 =num1 ^ num2 = 0b00000010 = 2
- num2 =num2 ^ num1 = 0b0000001 = 1
- num1 = num1 ^ num2 = 0b00000011 = 3
In [1]: def swap(num1, num2):
...: num1 ^= num2
...: num2 ^= num1
...: num1 ^= num2
...: return num1, num2
...:In [2]: num1 = 10In [3]: num2 = 20In [4]: num1, num2 = swap(num1, num2)In [5]: num1
Out [5]: 20In [6]: num2
Out [6]: 10
Check if an integer number is odd.
In a binary number, if LSB (Least Significant Bit.) is set as ‘1’ then that number is Odd else it’s even. To check LSB is ‘on’ or ‘off’ simply do ‘& 1’ with the number and if it returns 1 then LSB is set as ‘1’ else it’s ‘0’.
(num & 1) == 1Increment and Decrement by 1 (num — 1)
To increment Number by 1 using bitwise operations first do the (NOT) operation (~number) with the number then multiply with the ‘-’ sign to convert that number to a positive value.
Increment number By 1:
- num = 0b0000111 (7 in decimal)
- ~num = -0b00001000 (-8 in decimal)
- change sign of step2 by multiplying by ‘-’ sign. i.e. (-(-0b00001000)) = -(-8) = 8
In [1]: def addOne(x):
...: return (-(~x))
...:In [2]: print(addOne(13))
14In [3]: print(addOne(-13))
-12
Decrement number by 1:
To decrement the number first do left shift number by ‘1’ then add it with ‘~number’.
- num = 0b0000111 (7 in decimal)
- num << 1 = 0b00001110 (14 in decimal)
- ~(num) = -0b00001000 (-8 in decimal)
- add 2 and 3 step i.e (0b00001110 + -0b00001000) = (14+(-8)) = 6
In [1]: def subtractOne(x):
...: return ((x << 1) + (~x))
...:In [2]: subtractOne(10)
Out[2]: 9In [3]: subtractOne(-10)
Out[3]: -11
Flip the sign of an integer number.
To flip sign of any number just do NOT operation with the number and add 1 in it.
- num = 0b0000111 (7 in decimal)
- ~num = -0b00001000 (-8 in decimal)
- Add 1 in (step 2 )= 1+(0b00001000) = 1+(-8) = -7
In [1]: def flipSign(num):
...: return ~num + 1
...:In [2]: flipSign(10)
Out [2]: -10In [3]: flipSign(-10)
Out[3]: 10
This is it for now. In upcoming blog I will be covered more complex operations with bit’s. stay tuned.
