Rabi Siddique
787 words
4 minutes
Basics of Bit Manipulation

Bits And Binary Numbers#

A bit is the smallest unit of information that a computer can process. Each bit can hold one of two values: 0 or 1. In contrast, binary numbers represent a combination of bits and are based on the base-2 numeral system. This means binary numbers are composed using only two digits: 1 and 0. Each position in a binary number represents a power of 2, with the rightmost position being the lowest (2^0). Here is an example of how numbers are represented using 3 bits in binary:

Numbers in Binary#

Decimal NumberBinary Representation
0000
1001
2010
3011
4100
5101
6110
7111

This table illustrates how numbers from 0 to 7 are represented in a binary system using three bits. Each binary digit (bit) increases in value from right to left, each being a higher power of 2.

LSB and MSB in Binary Numbers#

In binary numbers, bits are indexed from right to left, with the rightmost bit being the least significant bit (LSB) and the leftmost bit being the most significant bit (MSB). Consider the binary number 101110011:

Bit Position876543210
Value101110011
  • The 0th bit (rightmost) is the LSB.
  • The 8th bit (leftmost) is the MSB.

Converting Binary Numbers to Decimal#

To convert the binary number 101 to decimal, follow this step-by-step process:

  1. Break down the binary number into its individual bits and assign powers of 2 to each bit from right to left, starting with (2^0) for the rightmost bit. Arrange this in a table for clarity:

    Bit ValuePower of 2Calculation
    1(2^2)(1 \times 4)
    0(2^1)(0 \times 2)
    1(2^0)(1 \times 1)
  2. Multiply each bit by its corresponding power of 2:

    • For the first bit: (1 \times 2^2 = 1 \times 4 = 4)
    • For the second bit: (0 \times 2^1 = 0 \times 2 = 0)
    • For the third bit: (1 \times 2^0 = 1 \times 1 = 1)
  3. Calculate the values of these multiplications:

    • The results from the step above are (4), (0), and (1).
  4. Add up the results:

    • Sum these values: (4 + 0 + 1 = 5)

The final sum, 5, is the decimal equivalent of the binary number 101.

Some Interesting Facts About Binary Numbers#

1. Even and Odd Numbers#

In binary, all even numbers have their least significant bit (the rightmost bit) set to 0. This means they end in 0. Conversely, odd numbers have their least significant bit set to 1, meaning they end in 1. For example:

  • 10 in binary is 2 in decimal.
  • 100 in binary is 4 in decimal.
  • 110 in binary is 6 in decimal.
  • 11 in binary is 3 in decimal.
  • 101 in binary is 5 in decimal.
  • 111 in binary is 7 in decimal.

2. Maximum Number Bits Can Represent#

The number of distinct values that can be represented with a set number of bits can be calculated using a simple formula. For example, with 4 bits, the range of representable numbers is from 0 to 15. This range is determined by the formula:

2^NumberOfBits - 1

Consider 4 bits:

  • 2^4 - 1 = 16 - 1 = 15

This calculation shows that 4 bits are capable of representing 16 different values (from 0 to 15).

3. Powers of 2 in Binary Numbers#

When all bits in a binary number are zero except one, this gives us a number which is power of 2. For instance, in the binary number 1000, the only 1 signifies 2^3, or 8.

4. Overflow#

Overflow in binary arithmetic happens when an addition or subtraction exceeds the number of bits available for storage. For example, adding 6 (110 in binary) and 5 (101 in binary) with only 3 bits available results in:

  110  (6 in binary)
+ 101  (5 in binary)
-------
 1011  (11 in binary)

This calculation should yield 11, but with only 3 bits, only numbers up to 7 can be represented. The result 1011 suggests overflow, as 11 exceeds the capacity of 3 bits.

5. Signed and Unsigned Integers#

Differentiating between signed and unsigned integers is important in binary arithmetic. In many programming environments, integers are typically represented using 32 bits.

  • Signed Integers: One bit is used to denote the sign (positive or negative), leaving 31 bits to represent the value. This setup impacts the maximum positive number that can be represented, calculated with:
  2^31 - 1

This formula accounts for the sign bit and correctly represents the highest number a 32-bit signed integer can store.

  • Unsigned Integers: All 32 bits are used to represent the magnitude of the number, allowing only non-negative values. The maximum number represented is thus:
  2^32 - 1

This configuration does not consider a sign bit and therefore can represent a broader range of positive numbers without the risk of overflow.

Useful Links#

Basics of Bit Manipulation
https://rabisiddique.com/posts/bit-manipulation/
Author
Rabi Siddique
Published at
2023-10-15