Programming Interviews Exposed: Secrets to Landing Your Next Job, 3rd Edition

Bit Manipulation

Most 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.

Binary Two’s Complement Notation

To work with bit operators, you need 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 very similar to plain binary notation. Actually, 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, this 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 simple. For example, you can add 00000001 (1) and 11111111 (–1) simply ...