On Bits

This article was originally written to help my CSCI 1302 students out on a project.

Binary to Decimal

Every non-negative binary number (base 2) has a corresponding decimal (base 10) expansion form. Consider a binary number with \( n \) bits, \( b_{n-1} \cdots b_1 b_0 \). This can be written in decimal as a sum of products:
$$ (b_{n-1} \cdot 2^{n-1}) + \cdots + (b_1 \cdot 2^1) + (b_0 \cdot 2^0) $$

As you can see, for every binary digit that is 1 we will add a power of 2 to the decimal representation. The power of 2 to be added corresponds to the placement of the binary digit (indexed from 0, starting on the right). If a binary digit is 0, then it will zero out its corresponding power of two, contributing nothing to the decimal expansion.
 
If you consider each product in the sum to be a component corresponding to a bit, then:

  • The the left hand side of the product represents the value of the bit (0 or 1).
  • The right hand side of the product (the power of 2) represents the digit placement of the bit. 

Consider the binary number \( 110 \). This expands to:  
$$ (1 \cdot 2^2) + (1 \cdot 2^1) + (0 \cdot 2^0) = 4 + 2 + 0 = 6 $$

Decimal to Binary

Check out the following site if you're unfamiliar with how to convert decimal numbers to their binary representation: http://www.wikihow.com/Convert-from-Decimal-to-Binary 
 
The link above shows two different methods for performing the conversion. The first method is analogous to the standard algorithm. The second method is one that may be quicker if performing the conversion by hand (e.g., on an exam) because it doesn't involve division. 

Toggling Bits

Let's assume you have an int called, "result," and you have a way of determining what a bit in its binary representation looks like. Now, suppose you want to toggle the bit at index \( i \) in order to change the value of result.

  • If \( b_i = 0 \), then to make it \( 1 \), you should add \( 2^i \) to result.
  • If \( b_i = 1 \), then to make it \( 0 \), you should subtract \( 2^i \) from result.

Hopefully this is obvious based on how the decimal expansion, explained earlier, works.

What is the bit at index \( i \)?

In order to toggle a binary bit, you need to first know if the bit is 0 or 1. To figure this out, we can utilize shifting (which will covered in more detail below). Let's assume you have an int called,  "result," and you have access to its binary digits. Now, suppose you want to determine if the bit at index \( i \) is equal to 1 (sometimes we say that the bit is set if it's equal to 1). 
 
The basic idea is that you shift the binary representation of the number to the right by \( i \) places, then check to see if the shifted number is odd. This works because the bit we want to check will end up being the first bit on the right after the shift. If the bit is 1, then the shifted number will be odd. If the bit is 0, then the shifted number will be even. This should make sense of you examine the decimal expansion of the shifted number.
 
Here is an example implementation:

boolean isSet(int number, int i) {
    return (number >> i) % 2 == 1; 
} // isSet

Bit Shifting

The left shift (<<) and right shift (>>) operators take an integer in its decimal representation, shift the bits in the integer's binary representation, then return the shifted integer in its decimal form. If a bit in the binary representation gets shifted off the edge in either direction, it's lost. Consider the integer \( 6 \) which has a binary representation of \( 110 \).
 
Shifting to the left shifts the bits to the left:

6 << 1 //   1100 equals 12
6 << 2 //  11000 equals 24
6 << 3 // 110000 equals 48

Shifting to the right shifts the bits to the right:

6 >> 1 // 11 equals 3
6 >> 2 //  1 equals 1
6 >> 3 //  0 equals 0

t should be noted that performing a left shift (<<) by \( i \) places is equivalent to multiplying the original number by \( 2^i \). Also, performing a right shift (>>) by \( i \) places is equivalent to dividing the original number by \( 2^i \) (integer division). This can be seen in the examples above, but can also be proved by examining the decimal expansion. 
 
Consider a number result with a binary representation containing \( n \) bits, \( b_{n-1} \cdots b_1 b_0 \). This can be written as:
 
result = \( (b_{n-1} \cdot 2^{n-1}) + \cdots + (b_1 \cdot 2^1) + (b_0 \cdot 2^0) \)
 
Now suppose we shift result to the left by \( i \) places. The binary expansion of this shifted number can be written as:
 
result << i = \( (b_{n-1} \cdot 2^{n-1+i}) + \cdots + (b_1 \cdot 2^{1+i}) + (b_0 \cdot 2^{0+i}) \)
 
To see how this works, consider the bit bj in the original number. Its contribution to the original decimal expansion is \( (b_j \cdot 2^j) \). If we were to shift it to the left by \( i \) places then we need to add \( i \) to its digit placement (its power of 2). This gives us \( (b_j \cdot 2^{j+i}) \) which can also be written as \( (b_j \cdot 2^j \cdot 2^i) \). It therefore follows that:
 
result << i = \( (b_{n-1} \cdot 2^{n-1+i}) + \cdots + (b_1 \cdot 2^{1+i}) + (b_0 \cdot 2^{0+i}) \)
result << i = \( (b_{n-1} \cdot 2^{n-1} \cdot 2^i) + \cdots + (b_1 \cdot 2^{1} \cdot 2^i) + (b_0 \cdot 2^{0} \cdot 2^i) \)
result << i = \( 2^i \cdot [ (b_{n-1} \cdot 2^{n-1}) + \cdots + (b_1 \cdot 2^{1}) + (b_0 \cdot 2^{0}) ] \)
result << i = \( 2^i \cdot \) result
 
Therefore:
 
result << i = \( 2^i \cdot \) result
 
A similar result can be shown for proving right shift is equivalent to dividing by a power of 2 by considering anything smaller than \( 2^0 \) to be 0. 

The cover image for this post is used under a CC BY-SA 2.0 license as described by its copyright holder @mcclanahoochie.