Bit manipulation is a lower-order (closer to metal!) approach to some common problems which is surprisingly easy with some basic understanding of binary numbers. I'll discuss bit manipulation and bitwise operations in another article - this article serves as a gentle introduction by walking through binary numbers first.
Bit manipulation is the technique of flipping 1's and 0's in binary representations (of numbers, letters, etc). So before we dive into bit manipulation, it is helpful to understand what binary numbers are.
Binary is simply a form of representing anything as a sequence of 1's and 0's. Those are the only two possible values at each bit in the representation.
Usually when an ordinary person thinks of a "normal" number, this number is a base 10 number. That is, the number is expressed as the addition of 100 (10 to the power 0) + some multiple of 101 (10 to the power 1) + some multiple of 102 (10 to the power 2) + some multiple of 103 (10 to the power 3), etc. For example, 583 (five hundred and eighty three) is expressed as:
(5 * 10**2) + (8 * 10**1) + (3 * 10**0)
= 500 + 80 + 3
= 583
Note! `10^2` is not how 102 (10 squared) is expressed in Python. 102 would be `10 ** 2`, while `10^2` (in Python) is using the bitwise XOR operator.
In binary, a similar expression is formed except that the number is in base 2. That is, the number is expressed as the addition of 20 (2 to the power 0) + some multiple of 21 (to to the power 1), etc. The binary number of 583 is therefore:
(2**9) + (2**6) + (2**2) + (2**1) + (2**0)
= 512 + 64 + 4 + 2 + 1
= 583
To represent that we want 29 + 26 + 22 + 21 + 20 in binary format, we place a 1 at the bit where we want the value and a 0 where we do not want the value. The bits at the far right represent 20, the second from the right represents 21, and so on. So the binary number for 583 is 1001000111.
In Python, the simple way to get this number is using the built in bin() function (note - this returns a binary string, not the binary bits), and using int() to convert back from binary to a base 10 integer.
bin(583) # '0b1001000111'
bin(583)[2:] # If you just want the digits without the '0b' prefix, ie '1001000111'
int('0b1001000111', 2) # ie second parameter (2) indicates the first parameter is in base 2 format.
int('1001000111', 2) # dropping the '0b' prefix works too.
0b1001000111 + 2 # 585. Python automatically converts binary numbers for mathematical operations.
When adding "normal" (base 10!) numbers, children are often taught if a particular digit is 10 or greater, to "carry over" the remainder. For example:
583
+ 637
====
1220 <==== Start by 3 + 7 = 10. Leave the 0, and "carry over" the 1 makes it 8 + 3 + 1 = 12. Leave the 2, "carry over" the 1, etc.
Similarly, when adding binary (base 2!) numbers, if the particular digit is 2 or greater, the remainder is "carried over". eg
101 <=== binary number for 5
+ 011 <=== binary number for 3
====
1000 <=== binary number for 8. Start with 1 + 1 = 2. This exceeds 2, so leave the 0 and "carry over" the 1 makes it 1 + 0 + 1 = 2. Leave the 0, "carry over" the 1, etc.