Advanced Programming Techniques (2011, 2013)

5. Counting Bits

73

A boolean variable, named after the British mathematician George Boole, is a variable that holds either false or true and nothing else. Sometimes within a program we have many boolean variables, perhaps hundreds or thousands. An efficient way to store many boolean variables is in a group called a bitset where each boolean variable is stored in a single bit with 0 meaning false and 1 meaning true. If a bit within a bitset holds 0, we say it isoff or clear, and if it holds 1, we say it is on or set.

One important operation that must be performed on a bitset is to count how many bits are set, which is sometimes called the population count. This chapter explores six different algorithms for computing the population count. Although counting bits is an important operation, it is unlikely you will ever be required to write code to do it. However, these six algorithms are highly instructive because they show very different approaches to the same problem, including straight forward or naive, combinatorial, and look-up.

Bitwise Operators

In order to understand the six population count algorithms, you must first understand the standard bitwise operations that a computer can perform. A bitwise operation is a manipulation of one or two binary numbers to produce another binary number. A bitwise operation processes one bit at a time, thus the name bitwise. There are seven standard bitwise operations that a computer can perform:

· left shift

· unsigned right shift

· signed right shift

· not

· and

· or

· exclusive or

The following examples are written in Java, but most programming languages have similar bitwise operators.

Left Shift

The left shift operator is two less than symbols (<<) and shifts all the bits in an integer to the left by a specified number of locations, filling the right-most bits with 0 and losing the values in the left-most bits. Arithmetically this is the same as multiplying an integer by a power of two. In other words, if the variable x holds an integer, x << n is equivalent to x * 2ⁿ.

Example 1

int x = 58;

int pos = x << 2; // 58 * 4 = 232

int z = -42;

int neg = z << 2; // -42 * 4 = -168

74

Unsigned Right Shift

The unsigned right shift operator (also called the logical right shift operator) is three greater than symbols (>>>) and shifts all the bits in an integer to the right by a specified number of locations, filling the left-most bits with 0 and losing the values in the right-most bits. Arithmetically this is the same as dividing any non-negative integer by a power of two. If the variable x holds a non-negative integer, then x >>> n is equivalent to using integer division to compute x / 2ⁿ.

Recall that integer division always truncates the quotient to an integer. In other words, integer division simply ignores the remainder. This is what right shift does. It shifts all the bits to the right, losing the right-most bits which is the same as dividing a non-negative integer by a power of two and ignoring the remainder.

Example 2

int x = 58;

int pos = x >>> 2; // 58 / 4 = 14

int z = -42;

int neg = z >>> 2; // -42 / 4 != 1,073,741,813

Signed Right Shift

In a two’s complement integer, the left-most bit is the sign bit and contains a 0 if the integer is non-negative and contains a 1 if the integer is negative. The signed right shift operator (also called the arithmetic right shiftoperator) is two greater than symbols (>>) and shifts all the bits in an integer to the right by a specified number of locations, filling the left-most bits with the value in the sign bit and losing the values in the right-most bits. Arithmetically this is the same as dividing any non-negative integer by a power of two. If the variable x holds a non-negative integer, then x >> n is equivalent to using integer division to compute x / 2ⁿ.

Example 3

int x = 58;

int pos = x >> 2; // 58 / 4 = 14

Because signed right shift preserves the value of the sign bit, it is also the same as dividing any negative integer by a power of two if no 1 bits are lost when shifting right. In other words if you use signed right shift to divide negative integers by 2 (x >> 1), the answer will be the same as integer division only half the time. If you use signed right shift to divide negative integers by 4 (x >> 2), the answer will be the same as integer division only one fourth of the time,

75

Example 4

int w = -40;

int ssrw = w >> 2; // -40 / 4 == -10

int x = -41;

int ssrx = x >> 2; // -41 / 4 != -11

int y = -42;

int ssry = y >> 2; // -42 / 4 != -11

int z = -43;

int ssrz = z >> 2; // -43 / 4 != -11

The best way to use right shift with all integers (positive and negative) and to get the same result as integer division by a power of 2 is to add 2^k − 1 to negative integers before using signed right shift, where k is the number of bits to shift right. The next example demonstrates signed right shift to divide a negative integer by 4.

Example 5

int x = -43;

if (x < 0) {

x += (1 << 2) - 1; // can be simplified to x += 3;

}

int div = x >> 2; // -43 / 2 == -10

76

Not

The bitwise not operator is the tilde (~) and takes an integer as input and clears every set bit and sets every clear bit, or in other words, switches every 1 bit to 0 and every 0 bit to 1.

Example 6

int x = 58;

int result = ~x;

And

The bitwise and operator is the ampersand (&) and takes two integers as input and produces an integer with bits set where the bits are set in both inputs and clear everywhere else. This is the same operation as logical and but performed on each bit. Within a program, bitwise and is often used to test if a bit is set and to clear bits in a variable.

Example 7

int x = 58;

int y = 107;

int result = x & y;

Or

The bitwise or operator is the vertical bar (|) and takes two integers as input and produces an integer with bits set where the bits are set in either or both inputs and clear everywhere else. This is the same operation as logical orbut performed on each bit. Within a program, bitwise or is often used to set bits in a variable.

Example 8

int x = 58;

int y = 107;

int result = x | y;

77

Exclusive Or

The bitwise exclusive or operator is the caret (^) and takes two integers as input and produces an integer with bits set where the bits in the two inputs are different and clear everywhere else. This is the same operation aslogical exclusive or but performed on each bit. Within a program, bitwise exclusive or is often used in data encryption and can even be used to swap the values of two variables.

Example 9

int x = 58;

int y = 107;

int result = x ^ y;

Shortcut Operators

All the bitwise operators, except not (~), can be combined with the assignment operator (=) to make shortcut operators as shown in the following examples.

Example 10

int x = 58;

x &= 0x0f;

x |= 0x70;

x ^= 0xb7;

x <<= 2;

x >>>= 1;

x >>= 1;

78

Example 11: Set and Clear Bits

int x = 58;

x |= (1 << 2); // Turn on bit #2

// Test if bit #2 is turned on

if ((x & (1 << 2)) != 0) {

System.out.println("bit 2 is set");

}

else {

System.out.println("bit 2 is clear");

}

x &= ~(1 << 3); // Turn off bit #3

Example 12: Switch the Values of Two Variables

int x = 58;

int y = -42;

// Exchange the values of x and y.

x ^= y;

y ^= x;

x ^= y;

Example 13: Encrypt and Decrypt a Short Message

// Encrypt the word "superb".

long plain = 0x0000737570657262L; // ASCII values for "superb"

long key = 0x36a1804be2f359e1L;

long cipher = plain ^ key; // encrypt

// The cipher text would be sent to a second party who

// would receive it and decrypt it using the same key.

long message = cipher ^ key; // decrypt

Now that you understand the bitwise operators, you are ready to learn the six population count algorithms.

79

Naive Bit Counting

A few years ago employees from a prominent software company would ask candidates during a job interview to write code to count the number of bits set to 1 in a 64-bit number. This is sometimes called the population count. Many candidates would write code similar to this naive Java code.

Example 14

/** Returns the number of bits set in a 64-bit word. */

public static int nbits(long word) {

int n = 0;

for (int i = 0; i != 64; ++i) {

if ((word & 1) != 0) {

++n;

}

word >>>= 1;

}

return n;

}

Improved Loop Termination

The interviewer would then show the candidate a faster way to solve the problem which was similar to this example.

Example 15

/** Returns the number of bits set in a 64-bit word. */

public static int nbits(long word) {

int n = 0;

while (word != 0) {

if ((word & 1) != 0) {

++n;

}

word >>>= 1;

}

return n;

}

Example 15 should be faster than example 14 because it eliminates incrementing the variable i, and it stops executing the loop when word reaches zero, meaning example 15 may not have to check all 64 bits. For example, consider this 64-bit number: 0x00 00 00 04 a0 3f 6e 8c. Example 15 will check only 35 bits and then stop, but example 14 will check all 64 bits before it finishes. Of course if a number has the highest order bit set, as is the case half of the time with random data, then example 15 isn’t much faster. So, example 15 is slightly faster than example 14 but only very slightly. There are several other algorithms for computing the population count which are substantially faster.

80

Addition Instead of If

Computers often execute if statements slowly because modern CPUs have a pipeline of instructions that are in the process of being decoded and executed. When the CPU begins executing an if-else statement, before it knows the value of the condition (true or false), it will predict that value (usually as true) and begin speculatively executing the statements in the corresponding part of the if-else statement. However, when the CPU finishes calculating the value of the condition, if it has predicted incorrectly, it must unload the instruction pipeline and begin executing the statements in the other part of the if-else statement which takes time. When an if statement does not have a matching else, the CPU must still predict whether the condition is true or false and speculatively execute statements according to its prediction. So to avoid the performance penalty of an if statement, example 16 replaces the ifstatement with a statement that adds 0 or 1. On my computer example 16 executes in about one third the time of example 15.

Example 16

/** Returns the number of bits set in a 64-bit word. */

public static int nbits(long word) {

int n = 0;

while (word != 0) {

n += (int)word & 1;

word >>>= 1;

}

return n;

}

Skip Zero Bits

This next example takes advantage of a feature of two’s complement arithmetic, namely: for any integer x, x &= (x - 1) deletes the right-most set bit in x. This means example 17 simply skips the 0 bits. For random values ofword about half the bits will be 0, so example 17 is about twice as fast as example 16 for random data.

Example 17

/** Returns the number of bits set in a 64-bit word. */

public static int nbits(long word) {

int n = 0;

while (word != 0) {

++n;

word &= word - 1;

}

return n;

}

81

Combinatorial Algorithm

Example 18 is based on algorithm 1.3, page 3 of “Combinatorial Algorithms, Theory and Practice”, by Edward M. Reingold, Jurg Nievergelt, and Narsingh Deo. This code is an example of a combinatorial algorithm or one that repeatedly combines intermediate results to arrive at the answer. Notice how this code repeatedly

1. shifts an integer to the right and uses a mask to extract every other bit (or every two bits or every four bits, etc),

2. uses the same mask to extract the other bits in the number, and

3. adds the bits, thus repeatedly combining intermediate results.

In essence, the code in example 18 uses a 64-bit processor as 32 2-bit processors, then 16 4-bit processors, then 8 8-bit processors, then 4 16-bit processors, 2 32-bits processors, and finally 1 64-bit processor to arrive at the answer. It runs in almost one fifth of the time of example 17.

Example 18

/** Returns the number of bits set in a 64-bit word. */

public static int nbits(long word) {

final long

ones = 0x5555555555555555L,

twos = 0x3333333333333333L,

fours = 0x0f0f0f0f0f0f0f0fL;

word = (word >>> 1 & ones) + (word & ones);

word = (word >>> 2 & twos) + (word & twos);

word = ((word >>> 4) + word) & fours;

word = (word >>> 8) + word;

word = (word >>> 16) + word;

word = (word >>> 32) + word;

return (int)word & 0xff;

}

82

Look Up Table

Finally example 19 separates a 64-bit number into 8 bytes and uses a look-up table to determine how many bits are set in each byte and adds those 8 quantities together. This example runs approximately as fast as example 18 but requires 256 bytes of memory for storing the look-up table.

Example 19

/** The number of bits set in a byte. */

private static final byte onbits[] = {

0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,

1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,

1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,

2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,

1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,

2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,

2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,

3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,

1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,

2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,

2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,

3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,

2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,

3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,

3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,

4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8

};

/** Returns the number of bits set in a 64-bit word. */

public static int nbits(long word) {

return onbits[(int)(word >>> 56)] +

onbits[(int)(word >>> 48) & 0xff] +

onbits[(int)(word >>> 40) & 0xff] +

onbits[(int)(word >>> 32) & 0xff] +

onbits[(int)(word >>> 24) & 0xff] +

onbits[(int)(word >>> 16) & 0xff] +

onbits[(int)(word >>> 8) & 0xff] +

onbits[(int) word & 0xff];

}

83

Algorithm Comparison

The following table compares all six of the algorithms presented in this chapter. Notice that the combinatorial and look up algorithms are 21 times faster than the naive algorithm. From the table, it is clear that example 18, the combinatorial algorithm, is the best overall choice of algorithms to count how many bits are set to 1 within an integer. Within the Java 1.6 libraries, the method Long.bitCount uses a slightly modified version of example 18.

and so on.