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.

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

Bitwise Operators

Most languages, especially the C-like ones, include a series of bitwise operators, operators that affect the individual bits of an integer value. C and C++ bitwise operators share the same syntax and behaviors. The bitwise operators in C#, Java, and JavaScript are the same as the C/C++ except for the shift operators.

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 remaining bit operators are the shift operators, operators that shift the bits within a value to the left or the right. C, C++, and C# have left (<<) and right (>>) shift operators. Java and JavaScript have one left shift (<<) operator but two right shift (>> and >>>) operators.

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 >> operator is also common to all five languages, but its behavior varies depending on what happens to the exposed bits on the left. When positive numbers are used, the result is always a positive number because 0’s are shifted into the empty spaces. However, negative numbers are treated differently. In C and C++, the value of a shifted negative number may be positive or negative, depending on the implementation. Therefore, 10100110 >> 5 may result in either 00000101 or 11111101. In C#, all the exposed bits except for the first bit are set to 0, but the first bit stays at 1 to keep the number negative. For example, 10100110 >> 5 results in 10000101. Java and JavaScript perform sign extension when shifting right, filling the empty spaces with 1’s for negative numbers, so 10100110 >> 5 becomes 11111101.

The >>> operator is unique to Java and JavaScript. It does a logical shift right, filling the empty spaces with 0 no matter what the value, so 10100110 >>> 5 becomes 00000101.

Optimizing with Shifts

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.




Programming Interviews Exposed. Secrets to Landing Your Next Job
Programming Interviews Exposed: Secrets to Landing Your Next Job, 2nd Edition (Programmer to Programmer)
ISBN: 047012167X
EAN: 2147483647
Year: 2007
Pages: 94

Similar book on Amazon
Cracking the Coding Interview: 150 Programming Questions and Solutions
Cracking the Coding Interview: 150 Programming Questions and Solutions
The Google Resume: How to Prepare for a Career and Land a Job at Apple, Microsoft, Google, or any Top Tech Company
The Google Resume: How to Prepare for a Career and Land a Job at Apple, Microsoft, Google, or any Top Tech Company
Programming Pearls (2nd Edition)
Programming Pearls (2nd Edition)
Algorithms For Interviews
Algorithms For Interviews

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net