[Tutor] Bitwise &

[Steven D'Aprano]

On Wed, Oct 14, 2015 at 01:47:02PM -0700, ਨਿਹੰਗ ਪੰਜਾਬੀ wrote:
>  'if (n & 1)'  below works but I don't understand why/how.  Kindly help.
> 
> ==============
> >>> def fn(n):
> ...     if (n & 1):
> ...         print "n is odd"
> ...     else:
> ...         print "n is even"

& is the "bitwise AND" operator. It takes each pair of bits (one from 
each of the two arguments) and combines them like this:

0 & 0 --> 0
0 & 1 --> 0
1 & 0 --> 0
1 & 1 --> 1

So if we take two numbers, say 25 and 43, and look at them in base 2 
(binary):

25 --> 011001 in binary
43 --> 101011 in binary

the & operator constructs a new binary number from each pair of bits. 
Starting from the left:

0 & 1 --> 0
1 & 0 --> 0
1 & 1 --> 1
0 & 0 --> 0
0 & 1 --> 0
1 & 1 --> 1

so the result of 25 & 43 is binary 001001 which equals 9 in 
decimal:

py> 25 & 43
9


Your function fn tests for odd numbers by using the bitwise AND of the 
number with 1. The binary (base 2) version of decimal 1 is 00000001 
(fill in as many leading zeroes as you need), so the result of n&1 will 
be 1 if the binary version of n ends with a 1 bit, otherwise 0.

So fn could be written like this (except it will probably be slower):

def fn(n):
    if bin(n).endswith("1"):
        print "n is odd"
    else:
        print "n is even"


Why does ending with a 1 bit mean that the number is odd? Here is a 
reminder about *decimal* numbers:

7453 in decimal means:

7 thousands (7 * 10**3)
4 hundreds (4 * 10**2)
5 tens (5 * 10**1)
3 units (3 * 10**0)

The binary number 111001 means:

1 * 2**5 = 32
1 * 2**4 = 16
1 * 2**3 = 8
0 * 2**2 = 0
0 * 2**1 = 0
1 * 2**0 = 1

Adding them together gives (32+16+8+1) = 57. Let's check if this is 
right:

py> int("111001", 2)
57

But the important thing to notice is that, in binary, every bit 
represents an *even* number, a power of 2: 2, 4, 8, 16, 32, 64, ...
EXCEPT the first bit (the one on the far right) which represents the 
number of units.

So if the far-right bit is 0, the number is an even number, and if the 
far-right bit is 1, the number is odd.

By the way, there is also a "bitwise OR" operator that uses this 
truth-table:

0 | 0 --> 0
0 | 1 --> 1
1 | 0 --> 1
1 | 1 --> 1

and a "bitwise XOR" (exclusive-or) operator:

0 ^ 0 --> 0
0 ^ 1 --> 1
1 ^ 0 --> 1
1 ^ 1 --> 0



-- 
Steve