Using bit operators

by Carl Burch, Hendrix College, August 2011

Using bit operators by Carl Burch is licensed under a Creative Commons Attribution-Share Alike 3.0 United States License.
Based on a work at www.toves.org/books/bitops/.

Contents

Internally, computers represent all data using bits: Each bit is an individual atom of memory that can be either off or on, which we interpret as 0 (off) or 1 (on). In this document, we'll study how computers use bits to represent integers — numbers with no fractional part, like 2, 105, or −38 — and we'll learn how a program can manipulate this integer representation directly using bit operators.

1. Numeral systems

Before we discuss the precise representation of integers in Section 2, we must first examine our basic numeral systems.

1.1. Binary numbers

You're already familiar with the decimal numeral system. You may remember the following sort of diagram from grade school.

This diagram has a line underneath each digit of the number 1024, and underneath each line is a reminder of how much that place is worth. In representing the number 1024, we have a 4 in the ones place, a 2 in the tens place, a 0 in the hundreds places, and a 1 in the thousands place. This system is also called base 10 because it is based on the number 10: There are 10 possible symbols for each place (0 through 9), and the place values go up by factors of 10 (1, 10, 100, 1000,…).

We call the 10 symbols 0 through 9 digits based on the Latin word for finger, because counting on fingers is the origin of our counting system. Of course, computers aren't endowed with such fingers, and so it shouldn't be surprising that this numeral system is less convenient for computers. Instead, computers count with bits, which have two possible states, and so we use a 2-based system — the binary numeral system.

In the binary numeral system, we have only two symbols 0 and 1, which we call bits based on contracting the phrase binary digit. Also, the place values go up by factors of 2, so our places are worth 1, 2, 4, 8, 16, and so on. The following diagrams a number written in binary notation.

This value, 1011₍₂₎, represents a number with 1 eight, 0 fours, 1 two, and 1 one: We perform the addition 1 ⋅ 8 + 0 ⋅ 4 + 1 ⋅ 2 + 1 ⋅ 1 = 11₍₁₀₎, and we conclude that this binary number 1011₍₂₎ is an alternative representation for the number we know as eleven, and which we write as 11 in decimal notation. (The parenthesized subscripts indicate whether the number is in binary notation or decimal notation.)

We'll often want to convert numbers between their binary and decimal representations. With 1011₍₂₎, we already saw one example of converting in the direction from binary to decimal. But here's another example: Suppose we want to identify what 100100₍₂₎ represents. We first determine what places contain the one bits.

We then add up the values of these places to get a base-10 value: The 32's place and the 4's place are filled with one bits, so we compute 32 + 4 = 36₍₁₀₎.

To convert a number from decimal to binary, we repeatedly determine the largest power of two that fits into the number and subtract it, until we reach zero; the binary representation has a 1 bit in each place whose value we subtracted, and a 0 bit in the remaining places. Suppose, as an example, we want to convert 88₍₁₀₎ to binary. We observe the largest power of 2 less than 88 is 64, so we decide that the binary expansion of 88 has a 1 in the 64's place, and we subtract 64 to get 88 − 64 = 24. Then we see than the largest power of 2 less than 24 is 16, so we decide to put a 1 in the 16's place and subtract 16 from 24 to get 8. Now 8 is the largest power of 2 that fits into 8, so we put a 1 in the 8's place and subtract to get 0. Once we reach 0, we write down which places we filled with 1's.

We put a zero in each empty place and conclude that the binary representation of 88₍₁₀₎ is 1011000₍₂₎.

1.2. Hexadecimal and octal

For humans, reading and typing binary numbers is a major hassle: The numbers tend to be long, and we're better with shorter numbers, even if there are more symbols to choose from. Computer programmers often find base 16 the most convenient choice — called the hexadecimal numeral system, often abbreviated as hex.

One of the first problems we face in talking about hexadecimal is that we need 16 different symbols for each digit, and we only know the 10 symbols 0 through 9. We fill out the remaining six symbols with letters from the alphabet:

A	is 10(10)		D	is 13(10)
B	is 11(10)		E	is 14(10)
C	is 12(10)		F	is 15(10)

Thus, we can plausibly talk about the number 1B4 in the hexadecimal system. Let's see what 1B4 translates to in decimal: As before, we first insert the place values, which now go up by factors of 16, starting with 1, 16, 256, and 4096.

We see that 1B4₍₁₆₎ has one 256, eleven 16's, and four 1's, so we compute 1 · 256 + 11 · 16 + 4 · 1 = 436₍₁₀₎. We conclude that 1B4₍₁₆₎ = 436₍₁₀₎.

But surely, you might object, decimal would be more convenient than hexadecimal! The special thing about hexadecimal is that it is based on a power of 2: 2⁴ = 16. This leads to a simple technique for converting between hexadecimal and binary, much quicker than anything available for decimal: We simply convert each hexadecimal digit into four bits.

Let's look at an example of this conversion using 1B4₍₁₆₎. We observe that the first digit 1 has the four-bit binary equivalent of 0001, the second digit B has the four-bit binary equivalent of 1011, and the third digit 4 has the four-bit binary equivalent of 0100. Put these together, and we arrive at the binary number 0001 1011 0100₍₂₎.

Going the other direction is just as easy. Let's consider the binary number 1011010110₍₂₎. We break it up into groups of four, starting from the bottom four bits, arriving at 10 1101 0110; and then we translate each group into the corresponding hexadecimal digit: 10₍₂₎ = 2, 1101₍₂₎ = 13₍₁₀₎ = D₍₁₆₎, and 0110₍₂₎ = 6. We therefore conclude that 1011010110₍₂₎ = 2D6₍₁₆₎.

Programmers also occasionally use base 8, called octal. Here, our digits are 0 through 7, and the place values are 1, 8, 64, 512, and so on. Thus 31₍₈₎ translates to three 8's and one 1, which is 3 · 8 + 1 · 1 = 25₍₁₀₎. (This leads to a simple joke: Why do programmers have a hard time distinguishing Halloween from Christmas? Because OCT 31 = DEC 25.)

Octal has the advantage that you can type it on a numeric keypad, but most programmers prefer hexadecimal — in part because groups of four bits conveniently pair into groups of eight, corresponding to the bytes that a computer uses.

These alternative bases are useful enough that C and its imitators (including Python and Java) have a special technique for incorporating octal and hexadecimal numbers into programs. If you prefix a number with the digit 0, then this indicates an octal number: 031 is an equivalent way of writing 25. Similarly, prefixing a number with the two-character sequence 0x indicates a hexadecimal number: 0x1b4 is equivalent to 436. When you see this in the program, it usually indicates that the programmer views the particular binary pattern as more important than its numeric value.

2. Integer representation

Now we can look at how computers actually store integers.

2.1. Unsigned integer representation

Modern computers represent all integers using the same amount of space. For example, we might decide that each byte represents a number. (A byte is a group of eight bits.) A byte, however, is very limiting: The largest number we can fit is 11111111₍₂₎ = 255₍₁₀₎, and we often want to deal with larger numbers than that.

Thus, computers tend to use groups of bytes called words. Different computers have different word sizes. In the past, many machines had 16-bit words; today, most machines use 32-bit words, though many use 64-bit words. (The term word comes from the fact that four bytes (32 bits) is equivalent to four ASCII characters, and four letters is the length of many useful English words.) Thirty-two bits is plenty for most numbers, as it allows us to represent any integer from 0 up to 2³² − 1 = 4,294,967,295. But the limitation is becoming increasingly irritating — primarily because it leads to problems when you have more than 4 gigabytes of memory (4 gigabytes is 2³² bytes) — and so larger systems frequently use 64-bit words.

The representation of an integer using binary representation in a fixed number of bits is called an unsigned representation. The term comes from the fact that the only numbers representable in the system have no negative sign.

But what about negative integers? After all, there are some perfectly respectable numbers below 0. We'll examine two techniques for representing integers both negative and positive: sign-magnitude representation and two's-complement representation.

2.2. Sign-magnitude representation

Sign-magnitude representation is the more intuitive technique. Here, we let the first bit indicate whether the number is positive or negative (the number's sign), and the rest of the bits tell how far the number is from 0 (its magnitude). Suppose we are working with 8-bit sign-magnitude numbers.

10	is represented as 00001010
−10	is represented as 10001010

For −10₍₁₀₎, we use 1 for the first bit, because the number is negative, and then we place 10₍₁₀₎ = 1010₍₂₎ into the remaining seven bits.

What's the range of integers we can represent with an 8-bit sign-magnitude representation? For the largest number, we'd want 0 for the sign bit and 1 everywhere else, giving us 01111111, or 127₍₁₀₎. For the smallest number, we'd want 1 for the sign bit and 1 everywhere else, giving us −127₍₁₀₎. An 8-bit sign-magnitude representation, then, can represent any integer from −127₍₁₀₎ to 127₍₁₀₎.

This range of integers includes 255 values. But we've seen that 8 bits can represent up to 256 different values. The discrepancy arises from the fact that the representation includes two representations of the number zero (0 and −0, represented as 00000000 and 10000000).

Arithmetic using sign-magnitude representation is somewhat more complicated than we might hope. To build a circuit comparing two numbers, you would need additional circuitry so that −0 is understood as equal to 0. Moreover, adding two numbers requires separate circuitry to handle the cases of when the numbers' signs match and when they don't match. Because of these complications, today's computers don't use sign-magnitude representation for integers. (It is used regularly in floating-point numbers, which are beyond the scope of this document.)

2.3. Two's-complement representation

Computers today use the two's-complement representation for integers. In the two's-complement system, the topmost bit's value is the negation of its meaning in an unsigned system. For example, in an 8-bit unsigned system, the topmost bit is the 128's place.

In an 8-bit two's-complement system, then, we negate the meaning of the topmost bit to be −128 instead.

If we were working with 32-bit numbers — as is typical — then we'd still negate the meaning of the topmost bit. In a 32-bit unsigned representation, the topmost bit is worth 2³¹, so in a 32-bit two's-complement representation, the topmost bit is worth −2³¹.

Let's see how a number is represented using two's-complement representation; we'll return to an 8-bit system, since it's easier to work examples there. We'll follow the same algorithm from Section 1.1 for converting from decimal to binary. Let's look at the example of −100₍₁₀₎. We first choose a 1 for the −128's place, leaving us with (−100) − (−128) = 28. (Since the place value is negative, we subtract a negative number.) Then we'd choose a 1 for the 16's place, the 8's place, and the 4's place to reach 0.

Thus, the 8-bit two's-complement representation of −100₍₁₀₎ would be 10011100.

To see the relationship between positive and negative representations, let's look at representing some numbers and their negations.

100	is represented as 01100100
−100	is represented as 10011100
10	is represented as 00001010
−10	is represented as 11110110

You see that the negation of a number involves flipping the first several bits of the number, but the last bits remain the same. For 100, we flip all but the last three bits; for 10, only the last two bits remain the same. The bits that remain the same include the last 1 and all succeeding 0's. That's a general rule for negating any two's-complement number: Flip all bits above the lowest 1.

What's the range of numbers representable in an 8-bit two's-complement representation? To arrive at the largest number, we'd want 0 for the −128's bit and 1 everywhere else, giving us 01111111, or 127₍₁₀₎. For the smallest number, we'd want 1 for the −128's bit and 0 everywhere else, giving −128₍₁₀₎. In an 8-bit two's-complement representation, we can represent any integer from −128₍₁₀₎ up to 127₍₁₀₎. This range includes 256 integers; there are no duplicates as with sign-magnitude representation.

It's instructive to map out the bit patterns (in order of their unsigned value) and their corresponding two's-complement values.

bits	value
00000000	0
00000001	1
00000010	2
:
01111110	126
01111111	127
10000000	−128
10000001	−127
:
11111110	−2
11111111	−1

Notice that the two's-complement representation wraps around: If you take the largest number, 01111111, and add 1 to it as if it were an unsigned number, you get 10000000, the smallest number. This wrap-around behavior can lead to some interesting behavior. In one game I played as a child (back when 16-bit computers were popular), the score would go up progressively as you guided a monster through a maze. I wasn't very good at the game, but my little brother mastered it enough that the score would hit its maximum value and then wrap around to a very negative value! Trying to get the largest possible score — without wrapping around — was an interesting challenge.

2.4. Adding two's-complement numbers

One of the nice things about two's-complement numbers is that you can add them just as you add regular numbers. Suppose we want to add −3 and 5.

We can attempt to do this using regular addition, akin to the technique we traditionally use in adding base-10 numbers, except that here adding 1 and 1 gives us 0 with a carry of 1, since 1 + 1 = 10₍₂₎.

We get an extra 1 in the ninth bit of the answer, but if we ignore this ninth bit, we get the correct answer of 2₍₁₀₎.

We can reason that ignoring this ninth bit is correct as follows: Say one of the two numbers is negative and the other is positive. That is, one of the two numbers has a 1 in the −128's place, and the other has 0 there. If there is no carry into the −128's place, then the answer is OK, because that means we got the correct sum in the lower 7 bits, and then when we add the −128's place, we'll maintain the −128 represented by the 1 in that location in the negative number.

If there is a carry into the −128's place, then this represents a carry of 128 taken from summing the 64's column. This carry of 128 (represented by a carry of 1), added to the −128 in that column for the negative number (represented by a 1 in that column), should give us 0. This is exactly what we get we add the carry of 1 into the leftmost column to the 1 of the negative number in this column and then throw away the carry.

A similar sort of analysis will also work when we are adding two negative numbers or two positive numbers. Of course, the addition only works if you end up with something in the representable range. There's no hope of arriving at a good answer if you add 120 and 120 with 8-bit two's-complement numbers, since the number 240 simply isn't representable in that system. (The answer turns out to be −16!)

The upshot of all this is that when building a circuit for two's-complement numbers, we don't need to worry about different cases needing different circuits: The circuit simply needs to do regular unsigned addition and then ignore the final carry (if any).

3. Bit operators

The representation of integers is important enough that programmers sometimes want the computer to manipulate integers' bits directly. They can do this using the bit operators, which we'll study in this section. We'll focus on the operators provided by C — though many other languages, including Python and Java, have copied the same symbols that C uses.

3.1. Bitwise operators

The most significant bit operators are the bitwise operators, which perform logic operations on all bits at once. For example, the bitwise NOT operator ~ (also called the bitwise complement) takes the NOT of all the bits in an integer. For example, if b holds the int value 00110111, then ~b flips all these bits to arrive at the int value 11001000.

The other bitwise operators are bitwise AND &, bitwise OR |, and bitwise XOR ^. These work by pairing corresponding bits in the two operands and performing the logical operation on them. For example, to compute the bitwise OR of 1100 and 1010, we take the OR of the first bit from each number (1, 1), followed by the OR of the second bits (1, 0), then the third bits (0, 1), then the fourth bits (0, 0). For each of these bit pairs, we include a 1 in the result if the first bit or the second bit in the pair is 1 (or if both are one). Thus, we end up with an output of 1110.

Similarly, the bitwise AND includes a 1 in the result if the first bit and the second bit in the pair is 1; the bitwise AND of 1100 and 1010 ends up being 1000. And the bitwise XOR (short for exclusive or) includes a 1 if the first bit or the second bit is 1 (but excluding the case that both bits are 1); the bitwise XOR of 1100 and 1010 ends up being 0110.

The following illustrates these operators at work.

int a = 0x23;        /* 00100011 */
int b = 0x36;        /* 00110110 */
printf("%x\n", ~a);
  /* prints DC (hex for 11011100) */
printf("%x\n", a & b);
  /* prints 22 (hex for 00100010) */
printf("%x\n", a | b);
  /* prints 37 (hex for 00110111) */
printf("%x\n", a ^ b);
  /* prints 15 (hex for 00010101) */

3.2. Bits as flags

So why would one want to use bitwise operators? One of the most important applications is to use an integer to hold a set of flags, where each bit corresponds to a different fact. A prime example of this comes from the Linux file system, where each file has a number called its mode that indicates who can access the file. If the 2's bit is set, then anybody can read the file; if the 4's bit is set, then anybody can modify the file; if the 128's bit is set, then the person who owns the file can read it; and if the 256's bit is set, then the person who owns the file can modify it. (The meanings for other bits are more complex.)

You might retrieve this integer in a program, but inevitably you will want to decode it. For example, what if our C program wants to check whether the owner has permission to modify a file? We would want to check whether the 256's bit is set. The most straightforward way to do this is to use the AND operator.

if ((mode & 256) != 0) {

By doing a bitwise AND with 256, we are making it so that only the 256's bit will remain — all other bits in 256 are 0, and anything ANDed with 0 is 0. The result will be 0 if mode's 256's bit is 0, since all other bits become 0 when ANDed with 256; and if mode's 256's bit is 1, the result will be nonzero. So our if statement compares the result of the bitwise AND with zero.

To a casual observer, the appearance of 256 here seems quite meaningless. So the header files define constants that correspond to each of the bits to allow us to refer to the bits in a less obscure way. For owner write permission, the constant 256 is named S_IWUSR — the W stands for write permission, and USR stands for the user; the S and I are simply to ensure that the constant's name is distinct from all other constants' names. So we'd instead write the following.

if ((mode & S_IWUSR) != 0) {

When we create a new file, we might want to indicate the permissions for this new file. For this, we would use the OR operator to combine several bits together.

creat("new_file.txt",
    S_IWUSR | S_IRUSR | S_IROTH);

(Yes, the function is named creat. Ken Thompson was once asked if he would do anything differently if he were to design UNIX again. He responded, ``I'd spell creat with an e.'')

This application of binary representation and bit operators extends beyond just file permissions. Three additional examples: An integer representation can indicate which of the mouse buttons and modifier keys are down, so when a program is responding to pressing a mouse button, it can retrieve a single number indicating the current combination, like control-right-click or shift-alt-left-click. Java's libraries also use flags for indicating whether a font is plain, bold, italic, or bold italic. And Python's re library uses flags for options on how regular expressions should be interpreted.

3.3. Shift operators

C provides two shift operators for shifting values: the left-shift operator << and the right-shift operator >>. These are binary operators, with the value to be shifted on the left side of the operator, and the distance to shift the value on the right side.

For example, the value of 5 << 2 is 20, since the binary representation of 5 is 101₍₂₎, which we shift left two spaces (and fill the empty spots with zeroes) to get 10100₍₂₎ = 20₍₁₀₎. Bits that go off the left end are simply lost. (Many programmers would say they fall into the bit bucket (or, more verbosely, the great bit bucket in the sky), a mythical location where bits go when they disappear.)

Notice that left-shifting by n bits is equivalent to multiplying by 2ⁿ, since we've essentially multiplied the value of each 1 bit in the number by that much. In the example of left-shifting 5 by 2, we get 5 ⋅ 2² = 20.

The right-shift operator works analogously: The value of 20 >> 2 is 5, since 20's binary representation is 10110₍₂₎, which shifted right two spots is 101₍₂₎ = 5. Again, the bits pushed off the right end simply fall into the bit bucket. Note that right-shifting is similar to dividing by a power of 2.

C doesn't specify how to handle right-shifting negative numbers. There are two common alternatives. In the first, called the logical right shift, a right-shift of a negative number will leave zeroes at the top end. The second, the arithmetic right shift, leaves ones on the top end for a negative number. Logical right shifts are more intuitive; but most compilers will use the arithmetic right shift, because programmers frequently want to use right-shift in place of dividing by a power of 2. If you take −24 and arithmetically right-shift by 2, you'd get −6.

(Java resolves this ambiguity by providing two separate right-shift operators: the arithmetic right-shift operator >> and the logical right-shift operator >>>.

int c = -20; // (11101100)
System.out.println(c >> 2);
 // prints -5 = 11111...1011
System.out.println(c >>> 2);
 // prints 1073741822 = 00111...10

The logical right shift produces a positive numeric value whose relationship to the original negative number is obscure.)

3.4. Operator hierarchy

The bit operators fit into the operator precedence hierarchy as follows.

~ ! + - (unary operators)

* / %

+ -

<< >> (and in Java, >>>)

< > <= >=

== !=

&

^

|

&&

||

conditional operator (?:)

= *= /= %= += -= <<= >>= &= ^= |=

At the bottom level, you can see that the bitwise and shift operators can be combined with the assignment operator, much like +=.

4. Counting one bits

Let's now ponder a popular programmers' puzzler: Write a function countOnes() that, given an int value, returns the number of bits in that number that are set to 1. For example, countOnes(21) should return 3, since 21's binary representation 10101₍₂₎ has three one bits in it. In fact, I visited Microsoft once interviewing for an internship, and one interviewer spent our appointment discussing various solutions to this question. (Many software companies like to spend interviews gauging interest and mastery using problems like this.)

4.1. Two simple techniques

The simplest technique is right-shift the number 32 times, counting the number of times you right-shift a one bit off.

int countOnesA(int num) {
    int ret = 0;
    int cur = num;
    int i;
    for (i = 0; i < 32; i++) {
        ret += cur & 1;
        cur >>= 1;
    }
    return ret;
}

A similar alternative checks each bit of the number from right to left.

int countOnesB(int num) {
    int ret = 0;
    int mask = 1;
    int i;
    for (i = 0; i < 32; i++) {
        if ((num & mask) != 0) ret++;
        mask <<= 1;
    }
    return ret;
}

Note the importance of the parentheses in the if condition: If they were omitted, then the compiler would interpret the expression as num & (mask != 0), since the operator hierarchy places != above &. Because C treats Boolean expressions as integers, this would compile fine, but it would not be what is desired. Many programmers always place parentheses around the Boolean operators because their precedence can result is such unexpected behavior.

4.2. A clever technique

In my interview at Microsoft, I composed essentially countOnesB(), which impressed the interviewer well enough. But then he showed me a different technique, which I have to admit is pretty clever.

This more clever technique employs the observation that, when you subtract a number by 1, all of the lowest bits change up to and including the lowest 1 bit; but the rest of the bits stay the same. So if I do a bitwise AND of n with n − 1, essentially I will remove the last one bit from n.

Once we observe this, we have only to write code that counts how many times we can remove the final bit in this way before we reach a number with no 1 bits at all (i.e., 0).

int countOnesC(int num) {
    int ret = 0;
    int cur = num;
    while (cur != 0) {
        cur &= cur - 1;
        ret++;
    }
    return ret;
}

4.3. A cleverer technique

Much later, I heard of yet another technique, which is yet more clever.

int countOnesD(int num) {
    int ret;
    ret = (num & 0x55555555)
        + ((num >> 1) & 0x55555555);
    ret = (ret & 0x33333333)
        + ((ret >> 2) & 0x33333333);
    ret = (ret & 0x0F0F0F0F)
        + ((ret >> 4) & 0x0F0F0F0F);
    ret = (ret & 0x00FF00FF)
        + ((ret >> 8) & 0x00FF00FF);
    ret = (ret & 0x0000FFFF)
        + ((ret >> 16) & 0x0000FFFF);
    return ret;
}

The first assignment statement begins with num & 0x55555555. The appearance of 0x55555555 may seem rather random, but recall that its binary representation alternates between zeroes and ones: 0101010101…. The bitwise AND of num with this number gives a version of num where every other bit (the 2's bit, the 8's bit, the 32's bit) has been removed and the remaining bits (1's, 4's, 16's, …) are kept. We'll call this result a.

The right side of this first addition, which we'll call b, involves right-shifting num once and then finding the bitwise AND of this. The result includes all the bits omitted from a, but shifted so that they they line up with a's bits, in the 1's place, 4's place, 16's place, and so on.

This first addition then adds these two results a and b together. The result, placed into ret, has each pair of bits holding the sum of that pair of bits in the original value of num. Let's look at an 8-bit example, 01110110.

num	01110010
a = num & 0x55	01010000
b = (num >> 1) & 0x55	00010001
ret = a + b	01100001

Notice how the first two bits from num are 0 and 1, and the first two bits from the result are 01, which is 0 + 1. The next two bits from num are 1 and 1, and the next two bits from the result are 10, which is 1 + 1. And so on.

Notice what has happened here: In a single addition operation, we have managed to perform 16 different bit-additions at the same time.

Now we proceed to add pairs of bits. Finding ret & 0x33333333 zeroes out every other pair of bits, leaving only the bottom pair (1's and 2's places), the third pair from the bottom (16's and 32's places), and so on. And (ret >> 2) & 0x33333333 finds all the remaining pairs, shifted so they are parallel to ret & 0x33333333. We now add these two groups of pairs together, and we end up with each group of four bits containing the sum of the two pairs previously in those four bits. Let's continue with our example.

ret	01100001
a = ret & 0x33	00100001
b = (ret >> 2) & 0x33	00010000
ret = a + b	00110001

Now the first four bits (0011) contain the sum of the first pair of bits from the original ret (01) and the second pair (10); and the second four bits (0001) contain the sum of the third pair (00) and the fourth pair (01). In the original value of num, the three of the first four bits were 1, and now the first four bits contain the number 3 in binary; likewise, the lower four bits in the original num contained one 1 bit, and now the lower four bits contain the number 1 in binary. This is not a coincidence.

The countOnesD() function continues, adding the groups of four bits together, then the groups of eight bits together, and finally the two groups of sixteen bits together. At the end, we have the total number of 1 bits in the original number.

4.4. Comparing techniques

The countOnesD() technique is clever, but is it really faster? To compare the efficiency of each of the techniques, we'll count the total number of operations in each function, ignoring assignments.

• For countOnesA(), each iteration includes five operations: a less-than comparison for the for loop, a bitwise AND and addition in the first line of the loop's body, a right-shift in the second line, and an addition as we increment i for the next iteration. With five operations per iteration for each of 32 bits, we have 32 · 5 = 160 operations.

• For countOnesB(), each iteration includes five or six operations: a less-than comparison for the for loop, a bitwise AND and a not-equals comparison for the if statement, possibly an addition if we execute the if statement's body, a left-shift operation for the second line of the loop's body, and an addition as we increment i for the next iteration. We don't know how often the if statement's body will be executed, but let's estimate that half of the bits will be 1's. The number of operations then would be 16 · 5 + 16 · 6 = 176 operations.

• For countOnesC(), each iteration includes four operations: a not-equals comparison for the while condition, a subtraction and a bitwise AND for the loop's first statement, and an addition as we increment ret. The number of iterations will match the number of 1 bits in the number, which we estimate will be true for 16 of the 32 bits. So there would be 16 · 4 = 64 operations.

• Finally, for countOnesD(), each assignment statement involves four operations: two bitwise ANDs, a right-shift, and an addition. There are five assignment statements, for 5 · 4 = 20 operations.

Based on this analysis, we'd surmise that countOnesD() would be about three times faster than countOnesC(), which itself is almost three times faster than countOnesA() or countOnesB().

That's the theoretical approach, but you might wonder about the actual performance. I ran a test involving running each of these four functions across 131,072 random numbers, using a Linux computer with an Intel Core i5 750 processor [test code]. Here is the average time per function call.

countOnesA():	68.8 ns
countOnesB():	83.1 ns
countOnesC():	16.0 ns
countOnesD():	0.9 ns

While the times here don't match the exact ratios our theory predicted, the conclusion remains the same: The cleverness of countOnesD() pays off.

By this point, you should have gained a basic familiarity with both integer representation and bit operators, the two key concepts behind what is sometimes pejoratively called bit twiddling, but which expert developers would agree is a key skill of proficient programmers.