Basics 0/108

Lesson 9 of 9 Advanced

Bit manipulation

Read and change bits with AND, OR, XOR, NOT, shifts and two's complement, count 1 bits with n & (n - 1), and answer array questions one bit at a time.

4,859 words · 22 min read

Part 1 of 10 Eight lights in one number

A row of lights stored as one number

A room has eight lights, numbered 0 to 7, and lights 0, 2 and 3 are on. A program could store the room as a list of eight true-or-false values. It could also write a 1 for each light that is on and a 0 for each light that is off, with light 0 at the right end, and read the row as one number in binary:

light   7  6  5  4  3  2  1  0on?     0  0  0  0  1  1  0  1

In base 2, 13 is written 1101. With four zeros in front, that is this row, so the number 13 holds the whole room. A number used this way, as a row of yes-or-no answers, is called a bitmask, or mask for short.

The reason to store the room as a number is that a computer works on every binary digit of a number in one step. Comparing two rooms stored as lists takes eight comparisons, and comparing two numbers takes one. An integer with 64 binary digits holds 64 lights, and one operation still handles all of them.

The operations that do this are the bitwise operators: AND, OR, XOR, NOT and two shifts. This lesson teaches them on the room, and then uses them to count the 1s in a number, to find the one value in a list that has no partner, and to count the differing bits over every pair of numbers in a list.

Bits and place values

A binary digit is called a bit. We number the bits from the right, starting at 0, so bit kk is light kk. Each place is worth twice the place to its right: bit 0 is worth 1, bit 1 is worth 2, bit 2 is worth 4, and bit kk is worth 2k2^k. The value of the number is the sum of what its 1 bits are worth. In the room, bits 3, 2 and 0 are 1:

13=23+22+20=8+4+113 = 2^3 + 2^2 + 2^0 = 8 + 4 + 1

In the same way, 00101100 has 1s at bits 5, 3 and 2, so it is 32+8+4=4432 + 8 + 4 = 44. This lesson writes numbers with 8 bits, which covers 0 to 255. Zeros in front do not change the value.

Definition

Bit kk of a nonnegative integer is its binary digit worth 2k2^k, counting from bit 0 at the right. A bit equal to 1 is a set bit.