Many computer languages have facilities to allow programmers access to the individual bits of a variable. Bit operators may appear more frequently in interviews than in day-to-day programming, so they merit a review. It’s very common to be presented with a “bit twiddling” problem early in the interview, as the problems tend to be short and may have multiple possible answers that enable the interviewer to probe the depth of your knowledge.
To work with bit operators, you have to start thinking on the levels of bits. Numbers are usually internally represented in a computer in binary two’s complement notation. If you’re already familiar with binary numbers, you almost understand binary two’s complement notation, because binary two’s complement notation is almost the same as plain binary notation. In fact, it’s identical for positive numbers.
The only difference appears with negative numbers. (An integer usually consists of 32 or 64 bits, but to keep things simple the example uses 8-bit integers.) In binary two’s complement notation, a positive integer such as 13 is 00001101, exactly the same as in regular binary notation. Negative numbers are a little trickier. Two’s complement notation makes a number negative by applying the rule “flip each bit and add 1” to the number’s positive binary representation. For example, to get the number –1, you start with 1, which is 00000001 in binary. Flipping each bit results in 11111110. Adding 1 gives you 11111111, which is the two’s complement notation for –1. If you’re not familiar with this, it may seem weird, but it makes addition and subtraction very simple. For example, you can add 00000001 (1) and 11111111 (-1) simply by adding the binary digits from right to left, carrying values as necessary, to end up with (00000000) 0.
The first bit in binary two’s complement notation is a sign bit. If the first bit is 0, the number is non-negative; otherwise, it’s negative. This has important implications when shifting bits within a number.
The simplest bit operator is the unary operator (~) called NOT. This operator flips or reverses all the bits that it operates on. Thus, every 1 becomes a 0, and every 0 becomes a 1. For example, if ~ is applied to 00001101, then the result is 11110010.
Three other bitwise operators are | (OR), & (AND), and ^ (XOR). They are all binary operators applied in a bitwise fashion. This means that the ith bit of one number is combined with the ith bit of the other number to produce the ith bit of the resulting value. The rules for these operators are as follows:
&: If both bits are 1, the result is a 1. Otherwise, the result is 0. For example:
01100110 & 11110100 01100100
|: If either bit is a 1, the result is 1. If both bits are 0, the result is 0. For example:
01100110 | 11110100 11110110
^: If the bits are the same, the result is 0. If the bits are different, the result is 1. For example:
01100110 ^ 11110100 10010010
Don’t confuse the bitwise & and | operators with the logical && and || operators. The bitwise operators take two integers and return an integer result; the logical operators take two Booleans and return a Boolean result.
The value to the right of the operator indicates how many positions to shift the bits. For example, 8 << 2 means shift the bits of the value “8” two positions to the left. Bits that “fall off” either end of a value (the overflow bits) are lost.
The << operator is common to all five languages. It shifts the bits to the left, filling the exposed bits on the right with 0. For example, 01100110 << 5 results in 11000000. Note that the value can change sign depending on the state of the new first bit.
The shift operators enable you to multiply and divide by powers of 2 very quickly. For non-negative numbers, shifting to the right one bit is equivalent to dividing by 2, and shifting to the left one bit is equivalent to multiplying by 2. For negative numbers, it obviously depends on the language being used.
The equivalence of shifting and multiplying or dividing by a power of the base also occurs in the more familiar base 10 number system. Consider the number 17. In base 10, 17 << 1 results in the value 170, which is exactly the same as multiplying 17 by 10. Similarly, 17 >> 1 produces 1, which is the same as integer dividing 17 by 10.