Read: § 2.9 of the C Programming Language, Bitwise Operations pp 45-6

Binary And Bit Ops

Binary Format; Conversions To And From Decimal

Integers are stored in binary (base 2) format. There are just two digits 0 and 1. Place values go up by factors of 2. Below we display the right-most 4 places.

     _ _ _ _
           ^ one's place
         ^ two's place
       ^ four's place
     ^ eight's place

As discussed before integers come in different sizes.

type   number of bits (places)

char    8
short  16
int    32
long   64

Conversion from Binary to Decimal.

Example: Convert 01101011 Binary to Decimal.

Work from left to right. Start with sum=0. For each digit, double the sum and add the digit into the sum.

Working let to right.
pattern: sum *= 2;     sum += d;  where d is the digit

sum *= 2;  sum += 0;   so sum=0
sum *= 2;  sum += 1;   so sum=1
sum *= 2;  sum += 1;   so sum=3
sum *= 2;  sum += 0;   so sum=6
sum *= 2;  sum += 1;   so sum=13
sum *= 2;  sum += 0;   so sum=26
sum *= 2;  sum += 1;   so sum=53
sum *= 2;  sum += 1;   so sum=107
107 Decimal is the equivalent value.

Convert from Decimal to Binary

Example: Convert 297 Decimal to Binary. Work from right to left. Start with num=297. Divide by 2. The remainder is the next binary digit. The quotient is tne new value for num. Stop when the quotient is 0. Below the expression num%2 is the remainder upon dividing num by 2. Variable num is unchanged. The expression num/=2 does change num. The new num is the (whole) number of times that 2 divides into the old num.

num=297                               Binary = ---------
r = num%2 = 1   q = (num /= 2) = 148  Binary = --------1
r = num%2 = 0   q = (num /= 2) =  74  Binary = -------01
r = num%2 = 0   q = (num /= 2) =  37  Binary = ------001
r = num%2 = 1   q = (num /= 2) =  18  Binary = -----1001
r = num%2 = 0   q = (num /= 2) =   9  Binary = ----01001
r = num%2 = 1   q = (num /= 2) =   4  Binary = ---101001
r = num%2 = 0   q = (num /= 2) =   2  Binary = --0101001
r = num%2 = 0   q = (num /= 2) =   1  Binary = -00101001
r = num%2 = 1   q = (num /= 2) =   0  Binary = 100101001

Bitwise Operations

Bitwise operations are operations that apply to the bits in integers.
Let a and b be integers. The operations below give us new integers.

a & b
a | b
a ^ b
~a

The & (and) operation, the | (or) operation, and the ^ (exclusive or) operation apply to corresonding bits in a and b. The result of & is 0 unless both corresponding bits are 1. The result of | is 1 unless both corresponding bits are 0. The result of ^ is 0 unless corresponding bits are different. The result of ~ is to make 0 bits into 1 bits and 1 bits into 0 bits.

Example.

a = 18 = 00010010 Binary
b =  6 = 00000110 Binary

a & b =  00000010 Binary =   2
a | b =  00010110 Binary =  22
a ^ b =  00010100 Binary =  20
~a    =  11101101 Binary = 237

Numbering The Bits

Bits are counted from right to left. The right-most bit is bit 0. It is also called the 1's place. Note: 1 is 2 raised to the exponent 0. This continues: the next bit is bit 1. It is also the 2's place and 2 is 2 raised to the exponent 1. The next bit is bit 2. It is also the 4's place and 4 is 2 raised to the exponent 2.

Setting And Clearing Bits

Setting a bit means making the bit a 1. Clearing a bit means making a the bit a 0.

Example.

a = b = 18 = 00010010 Binary
 
a |= 8;   //sets  bit 3 of a; note 8 is 2 raised to exponent 3; a is now 26

b &= (~16); //clears bit 4 of b; Note 16 is 2 raised to exponent 4; b is now 2

Shifts

There are two shifts. Format:

  expression >> shift_amount
  expression << shift_amount

Operation >> is a shift right of the bits of the expression.
Example:

a = 18 = 00010010 Binary
a >> 2

The value is the value of the expression but shifted two bits to the right. The two right-most bits are lost; Two new 0 bits come in on the left

a >> 2 = 00000100 Binary = 4

Operation << is a shift left of the bits of the expression.
Example:

a = 18 = 00010010 Binary
a << 4

The value is the value of the expresssion but shifted 4 bits left. 4 0's are brought in on the right and the left-most 4 bits are lost.

a << 4 = 00100000  Binary = 32

next: More Control (Constructs)