[Tutor] Bitwise &
Steven D'Aprano
steve at pearwood.info
Wed Oct 14 20:26:31 EDT 2015
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
More information about the Tutor
mailing list