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

11.2. Bit Manipulation

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.

11.2.1. Binary Two's Complement Notation

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