Bit-wise operations tactics.

Parag Kamble
7 min readSep 1, 2021

--

Image Credit : Pixabay

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.

  1. ~Bitwise NOT
  2. &Bitwise AND
  3. |Bitwise OR
  4. ^Bitwise XOR
  5. <<Left Shift
  6. >>Sign-Propagating Right Shift
  7. >>>Zero-Fill Right Shift

Manipulating bit.

Turn off Rightmost 1-bit in the word. e.g ( 01001000 => 01000000).

Steps:

  1. Subtract 1 from the original word. (0b01001000 -1 = 0b1000111)
  2. 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:

  1. Add 1 to the original word (0b10100100+1 = 0b10101000)
  2. 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:

  1. Add 1 to the original word (0b10100111+1 = 0b10101000)
  2. 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:

  1. Subtract 1 from the original Word (0b10101000–1 = 0b10100111).
  2. 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.

  1. 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:

  1. First create bit mask for that particular position.
  2. 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 = 0b10000000

And the state of all LED’s get stored in below variable. Initially I am setting all LED’s to ‘On’ Position.

STATE = 0b11111111

Now 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.

  1. num1 = 0b00000001 (1 in decimal) ; num2 = 0b00000011 = 3
  2. num1 =num1 ^ num2 = 0b00000010 = 2
  3. num2 =num2 ^ num1 = 0b0000001 = 1
  4. 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]: 20
In [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) == 1

Increment 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:

  1. num = 0b0000111 (7 in decimal)
  2. ~num = -0b00001000 (-8 in decimal)
  3. 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))
14
In [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’.

  1. num = 0b0000111 (7 in decimal)
  2. num << 1 = 0b00001110 (14 in decimal)
  3. ~(num) = -0b00001000 (-8 in decimal)
  4. 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]: 9
In [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.

  1. num = 0b0000111 (7 in decimal)
  2. ~num = -0b00001000 (-8 in decimal)
  3. Add 1 in (step 2 )= 1+(0b00001000) = 1+(-8) = -7
In  [1]: def flipSign(num):
...: return ~num + 1
...:
In [2]: flipSign(10)
Out [2]: -10
In [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.

--

--

Parag Kamble
Parag Kamble

Written by Parag Kamble

Quality Engineer, Performance Engineer, Distributed Systems, Robotics.

No responses yet