Bit Twiddling in Python
Bit Twiddling in Python
One thing I love about Python is that I don’t have to do too much C coding anymore. While I still use C to implement cryptography methods that need to run fast, most of the time I just implement my code in Python. If I need the program to run as fast as C, there’s always Golang. And with Python, I can do all the normal bit twiddling methods that I would normally do in C.
Bit shifting
In cryptography, and in many other areas, we often use bit shifting, and where we take all the bits and move them to the right or the left. If the bits that fall of the start or end are fed back into the other side, we define that as a rotate left (ROL) or a rotate right (ROR), otherwise, it is a shift left or a shift right. In Python, the operators for shifting are “<<” (shift left) and “>>” (shift right).
In the following we implement shifts on a given value [here]:
import sys
val1="00110101"
if (len(sys.argv)>1):
val1=sys.argv[1]
print ("Binary form: \t\t",val1)
dec=int(val1,2)
print ("Decimal form: \t\t",dec,"\t",bin(dec)[2:10].rjust(8,'0'))
res=(dec << 1) & 0xff
print ("Shift left (1):\t",res,"\t",bin(res)[2:10].rjust(8,'0'))
res=(dec << 2) & 0xff
print ("Shift left (2):\t",res,"\t",bin(res)[2:].rjust(8,'0'))
res=(dec >> 1) & 0xff
print ("Shift right (1):\t",res,"\t",bin(res)[2:10].rjust(8,'0'))
res=(dec >> 2) & 0xff
print ("Shift right (2):\t",res,"\t",bin(res)[2:10].rjust(8,'0'))A sample run is for an input of 53 is [here]:
Binary form: 00110101
Decimal form: 53 00110101
Shift left (1): 106 01101010
Shift left (2): 212 11010100
Shift right (1): 26 00011010
Shift right (2): 13 00001101Notice that the bits that are shifted out of the eight-bit window, are replaced by a zero at the other end. If we wanted to move them onto the other end, we would have to manually do this in the code (as Python does not support this operation directly).
Bit-masking
The AND bitwise operator can be used to mask bits off. We often use the AND bitwise operation to mask off some bits, as a 0 in a certain bit position will make the result ‘0’, while a ‘1’ at this position will preserve the value of the bit. For example, the following are bit masks for 1, 2 and 3:
128 64 32 16 8 4 2 1 Decimal
b7 b6 b5 b4 b3 b2 b1 b0
Val 0 0 1 1 0 1 0 1 53
Val & 0x1 0 0 0 0 0 0 0 1 1
Val & 0x2 0 0 0 0 0 0 1 0 2
Val & 0x3 0 0 0 0 0 0 0 1 1
The following takes a value and then bit masks from 0 (b0000000)to 255 (b11111111) [here]:
import sys
val1="00110101"
if (len(sys.argv)>1):
val1=sys.argv[1]
dec=int(val1,2)
print ("Decimal form: \t\t",dec,"\t",bin(dec)[2:10].rjust(8,'0'))
print ("Mask\tBinary\tResult")
print ("---------------")
for i in range(0,255):
print (f"{i}\t{bin(i)[2:10].rjust(8,'0')}\t{bin(dec & i)[2:10].rjust(8,'0')}")A sample run is [here]:
Decimal form: 53 00110101
Mask Binary Result
--------------------------------
0 00000000 00000000
1 00000001 00000001
2 00000010 00000000
3 00000011 00000001
4 00000100 00000100
5 00000101 00000101
6 00000110 00000100
7 00000111 00000101
8 00001000 00000000
9 00001001 00000001
10 00001010 00000000
11 00001011 00000001
12 00001100 00000100
13 00001101 00000101
14 00001110 00000100
15 00001111 00000101
16 00010000 00010000
...
247 11110111 00110101
248 11111000 00110000
249 11111001 00110001
250 11111010 00110000
251 11111011 00110001
252 11111100 00110100
253 11111101 00110101
254 11111110 00110100
For example, if we bitwise AND “0011 0101” with “0000 1111” (which masks off the bit four bits) we get:
Val 0 0 1 1 0 1 0 1
& 0 0 0 0 1 1 1 1
------------------------------
0 0 0 0 0 1 0 1
which results in “0000 0101”
Bit-mask to test a single bit
The AND bitwise operator can be used to mask bits off. We often use the AND bitwise operation to mask off some bits, as a 0 in a certain bit position will make the result ‘0’, while a ‘1’ at this position will preserve the value of the bit. For example, if we wish to mask bit 3 we can use:
if ((val & 0x08) == 0x08) print "Bit 3 is set to a 1"The code for this is [here]:
import sys
val1="00110101"
if (len(sys.argv)>1):
val1=sys.argv[1]
dec=int(val1,2)
print (f"Decimal form:\t\t{dec}\t{bin(dec)[2:10].rjust(8,'0')}")
print ("Bit\tResult")
print ("--------------------")
mask=1
for i in range(0,8):
if (dec & mask == mask):
print ("Bit",i," is set to 1")
else:
print ("Bit",i," is set to 0")
mask = mask <<1A sample run is [here]:
Decimal form: 240 11110000
Bit Result
--------------------
Bit 0 is set to 0
Bit 1 is set to 0
Bit 2 is set to 0
Bit 3 is set to 0
Bit 4 is set to 1
Bit 5 is set to 1
Bit 6 is set to 1
Bit 7 is set to 1
For example, if we bitwise AND “0011 1001” with “0000 1000” (which masks off the 4th bit) we get:
Val 0 0 1 1 1 0 0 1
& 0 0 0 0 1 0 0 0
------------------------------
0 0 0 0 1 0 0 0
which results in “0000 1000”. The result will thus be a value of 8 (if the bit is set to a 1) or 0 (if the bit is set to a zero).
Conclusions
Go twiddle some bits in Python! If you are interested, there’s more Python here: