Bitwise operators

Reading list

• Read Kernighan & Ritchie Page 48-49

• Lecture Slides

• Reading material from the course website

Binary Number System
And Conversion
 Bridging the Digital Divide
Decimal-to-Binary
Conversion

Binary-to-Decimal
Conversion

4
 Decimal ‒to‒ Binary Conversion
The Process : Successive Division
a) Divide the Decimal Number by 2; the remainder is the LSB of Binary
Number .
b) If the quotient is zero, the conversion is complete; else repeat step (a)
using the quotient as the Decimal Number. The new remainder is the
next most significant bit of the Binary Number.

Example:
Convert the decimal number 610 into its binary equivalent.

3
2 6 r  0  Least Significant Bit
1
2 3 r 1  610 = 1102
0
2 1 r  1  Most Significant Bit
5
 Dec → Binary : Example #1
Example:
Convert the decimal number 2610 into its binary equivalent.

6
 Dec → Binary : Example #1
Example:
Convert the decimal number 2610 into its binary equivalent.

Solution:
13
2 26 r  0  LSB
6
2 13 r 1
3
2 6 r 0  2610 = 110102
1
2 3 r 1
0
2 1 r  1  MSB

7
 Dec → Binary : Example #2
Example:
Convert the decimal number 4110 into its binary equivalent.

8
 Dec → Binary : Example #2
Example:
Convert the decimal number 4110 into its binary equivalent.

Solution:
20
2 41 r  1  LSB
10
2 20 r 0
5
2 10 r 0  4110 = 1010012
2
2 5 r 1
1
2 2 r 0
0
2 1 r  1  MSB 9
 Dec → Binary : More Examples

a) 1310 = ?

b) 2210 = ?

c) 4310 = ?

d) 15810 = ?

10
 Dec → Binary : More Examples

a) 1310 = ? 1 1 0 1 2

b) 2210 = ? 101102

c) 4310 = ? 1 0 1 0 1 1 2

d) 15810 = ? 100111102

11
 Converting it to 32 bits Binary
By padding with 0 from the left

a) 1310 = ? 0 0 0 0 …. 1 1 0 1 2

b) 2210 = ? 0 0 0 0 …. 1 0 1 1 0 2

c) 4310 = ? 0 0 0 0 .. … 1 0 1 0 1 1 2

d) 15810 = ? 0 0 0 0 … … 1 0 0 1 1 1 1 0 2
12
 Binary ‒to‒ Decimal Process
The Process : Weighted Multiplication
a) Multiply each bit of the Binary Number by it corresponding bit-
weighting factor (i.e. Bit-0→20=1; Bit-1→21=2; Bit-2→22=4; etc).
b) Sum up all the products in step (a) to get the Decimal Number.

Example:
Convert the decimal number 01102 into its decimal equivalent.

0 1 1 0
23 22 21 20
Bit-Weighting  0110 2 = 6 10
8 4 2 1 Factors

0 + 4 + 2 + 0 = 610

13
 Binary → Dec : Example #1
Example:
Convert the binary number 100102 into its decimal equivalent.

14
 Binary → Dec : Example #1
Example:
Convert the binary number 100102 into its decimal equivalent.

Solution:

1 0 0 1 0
24 23 22 21 20

16 8 4 2 1

16 + 0 + 0 + 2 + 0 = 1810

100102 = 1810

15
 Binary → Dec : Example #1
Example:
Convert the binary number 100102 into its decimal equivalent.

Solution:

1 0 0 1 0
24 23 22 21 20

16 8 4 2 1

16 + 0 + 0 + 2 + 0 = 1810

100102 = 1810

16
 Binary → Dec : Example #2
Example:
Convert the binary number 01101012 into its decimal
equivalent.

17
 Binary → Dec : Example #2
Example:
Convert the binary number 01101012 into its decimal
equivalent.

Solution:

0 1 1 0 1 0 1
26 25 24 23 22 21 20

64 32 16 8 4 2 1

0 + 32 + 16 + 0 + 4 + 0 + 1 = 5310

01101012 = 5310

18
 Binary → Dec : More Examples

a) 0110 2 = ?

b) 11010 2 = ?

c) 0110101 2 = ?

d) 11010011 2 = ?

19
 Binary → Dec : More Examples

a) 0110 2 = ? 6 10

b) 11010 2 = ? 26 10

c) 0110101 2 = ? 53 10

d) 11010011 2 = ? 211 10

20
 Summary & Review
Successive
Division

a) Divide the Decimal Number by 2; the remainder is the LSB of Binary

Number .
b) If the Quotient Zero, the conversion is complete; else repeat step (a) using
the Quotient as the Decimal Number. The new remainder is the next most
significant bit of the Binary Number.

Weighted
Multiplication

a) Multiply each bit of the Binary Number by it corresponding bit-weighting

factor (i.e. Bit-0→20=1; Bit-1→21=2; Bit-2→22=4; etc).
b) Sum up all the products in step (a) to get the Decimal Number.
21
 Bit wise operators in C
~  complement
Flips bits,
0 becomes 1 and
1 becomes 0
a = 13 = 00000 … .. 000001101
~a = 11111 … .. 11111 0010
Bit wise operators in C

&  and
|  or
^  xor
<<  left shift
>>  right shift
 Laws of operators
Suppose a is an 1-bit number
(i.e., 0 or 1)
a&00 a|0a a^0a

a&1a a|11 a ^ 1  ~a

a&aa a|aa a^a0

 Laws of operators
Suppose a is an 1-bit number
(i.e., 0 or 1)

a&00

a&1a

a&aa
 Laws of operators
Suppose a is an 1-bit number
(i.e., 0 or 1)

a|0a

a|11

a|aa
 Laws of operators
Suppose a is an 1-bit number
(i.e., 0 or 1)
a^0a

a ^ 1  ~a

a^a0
 x  6

y5

x&y?

x  6  0000 …. 0000 0110

y  5  0000 …. 0000 0101

------------------------------------------
x&y  0000 …. 0000 0100  4
 x  6

y5

x|y?

x  6  0000 …. 0000 0110

y  5  0000 …. 0000 0101

------------------------------------------
x|y  0000 …. 0000 0111  7
 x  6

y5

x^y?

x  6  0000 …. 0000 0110

y  5  0000 …. 0000 0101

------------------------------------------
x^y  0000 …. 0000 0011  3
 Filled it with 0

For signed numbers filled it with 1

 Some quick examples
Determining a number odd or even? No logical
operators can be used p
ODD

31 30 29 28 9 8 7 6 5 4 3 2 1 0

0 1 0 0 … 0 1 0 0 0 1 1 0 1 1

Even p

31 30 29 28 9 8 7 6 5 4 3 2 1 0

0 1 0 0 … 0 1 0 0 0 1 1 0 1 0
int main(){
int x,m,y;
scanf(“%d”,&x);
m = 1;
if(x & m)
printf(“ODD”);
else
printf(“EVEN”);
return 0;
}
 Some quick examples
Determining whether a number is positive or negative?
Positive
p

31 30 29 28 9 8 7 6 5 4 3 2 1 0

0 1 0 0 … 0 1 0 0 0 1 1 0 1 1

Negative
p

31 30 29 28 9 8 7 6 5 4 3 2 1 0

1 1 0 0 … 0 1 0 0 0 1 1 0 1 1
int main(){
int x,m,y;
scanf(“%d”,&x);
m = 1 << 31 ; // m = 1 << 8*sizeof(int)-1
if(x & m)
printf(“NEGATIVE”);
else
printf(“POSITIVE”);
return 0;
}
 printBits(x)
Write down a function printBits(x) that will print the bit
patterns of an integer x
printBits(27)

31 30 29 28 9 8 7 6 5 4 3 2 1 0

0 0 0 0 … 0 0 0 0 0 1 1 0 1 1
x
int printBits(int x){
unsigned m;
m = 1 << (8*sizeof(int)-1);
for(int i = 1; i <= 8*sizeof(int); i++){
if(x&m)
printf("1");
else
printf("0");
m >>= 1;
if(i%4 == 0)
printf(" ");
}
printf("\n");
}
 setBit(x,p)
Write down a function setBit(x,p) that will set a bit of
integer x at position p leaving other bits unchanged and
return the value. Assume 0 ≤ p ≤31
p

31 30 29 28 9 8 7 6 5 4 3 2 1 0

0 1 0 0 … 0 1 0 0 0 1 1 0 1 1
x

setBit(x, 6)
 setBit(x,p)
Write down a function setBit(x,p) that will set a bit of
integer x at position p leaving other bits unchanged and
return the value. Assume 0 ≤ p ≤31
p

31 30 29 28 9 8 7 6 5 4 3 2 1 0

0 1 0 0 … 0 1 0 1 0 1 1 0 1 1
x

setBit(x, 6)
a|0a
a|11 setBit(x,p)
a|aa
Write down a function setBit(x,p) that will set a bit of
integer x at position p leaving other bits unchanged and
return the value. Assume 0 ≤ p ≤31

setBit(x, 6) p

31 30 29 28 9 8 7 6 5 4 3 2 1 0

0 1 0 0 … 0 1 0 0 0 1 1 0 1 1
x

31 30 29 28 9 8 7 6 5 4 3 2 1 0

m 0 0 0 0 … 0 0 0 1 0 0 0 0 0 0
int setBit(int x, int p){
int m,y;
m = 1 << p ;
y = x | m;
return y;
}
 setBits(x,p,n)

Write down a function setBits(x,p,n) that will set the n

bits of the integer x starting from position p leaving
other bits unchanged. Assume 0 ≤ p ≤31 and n ≤ p+1
p

31 30 29 28 9 8 7 6 5 4 3 2 1 0

0 1 0 0 … 0 1 0 0 0 1 1 0 1 1
x

setBits(x, 6, 3)
 setBits(x,p,n)

Write down a function setBits(x,p,n) that will set the n

bits of the integer x starting from position p leaving
other bits unchanged. Assume 0 ≤ p ≤31 and n ≤ p+1
p

31 30 29 28 9 8 7 6 5 4 3 2 1 0

0 1 0 0 … 0 1 0 1 1 1 1 0 1 1
x

setBits(x, 6, 3) Call setBit(x,p) in a

loop
int setBit(int x, int p){
int m,y;
m = 1 << p ;
y = x | m;
return y;
}

int setBits(int x, int p, int n){

int m,y;
for(i = 0; i < n; i++)
x = setBit(x,p-i);
}
 Efficient setBits(x,p,n)
p
setBits(x, 6, 3)
31 30 29 28 9 8 7 6 5 4 3 2 1 0

0 1 0 0 … 0 1 0 1 1 1 1 0 1 1
x
31 30 29 28 9 8 7 6 5 4 3 2 1 0

m 0 0 0 0 … 0 0 0 1 1 1 0 0 0 0

x|m
 Efficient eSetBits(x,p,n)

int eSetBits(int x, int p, int n){

int m;
m = ~(~0 << n) << (p-n+1);
return x|m;
}
 resetBit(x,p)
Write down a function resetBit(x,p) that will reset a bit
of integer x at position p leaving other bits unchanged.
Assume 0 ≤ p ≤31
p

31 30 29 28 9 8 7 6 5 4 3 2 1 0

0 1 0 0 … 0 1 0 1 0 1 1 0 1 1
x

resetBit(x, 6)
 resetBit(x,p)
Write down a function resetBit(x,p) that will reset a bit
of integer x at position p leaving other bits unchanged.
Assume 0 ≤ p ≤31
p

31 30 29 28 9 8 7 6 5 4 3 2 1 0

0 1 0 0 … 0 1 0 0 0 1 1 0 1 1
x

resetBit(x, 6)
a&00
a&1a resetBit(x,p)
a&aa
Write down a function resetBit(x,p) that will reset a bit
of integer x at position p leaving other bits unchanged.
Assume 0 ≤ p ≤31

resetBit(x, 6) p

31 30 29 28 9 8 7 6 5 4 3 2 1 0

0 1 0 0 … 0 1 0 1 0 1 1 0 1 1
x

31 30 29 28 9 8 7 6 5 4 3 2 1 0

m 1 1 1 1 … 11 1 1 0 1 1 1 1 1 1
int resetBit(int x, int p){
int m,y;
m = 1 << p ;
m = ~m;
y = x & m;
return y;
}
 resetBits(x,p,n)

Write down a function resetBits(x,p,n) that will reset the n

bits of the integer x starting from position p leaving other
bits unchanged. Assume 0 ≤ p ≤31 and n ≤ p+1
p

31 30 29 28 9 8 7 6 5 4 3 2 1 0

0 1 0 0 … 0 1 0 1 0 1 1 0 1 1
x

resetBits(x, 6, 3)
 resetBits(x,p,n)

Write down a function resetBits(x,p,n) that will reset the n

bits of the integer x starting from position p leaving other
bits unchanged. Assume 0 ≤ p ≤31 and n ≤ p+1
p

31 30 29 28 9 8 7 6 5 4 3 2 1 0

0 1 0 0 … 0 1 0 0 0 0 1 0 1 1
x

resetBits(x, 6, 3) Call resetBit(x,p) in

a loop
int resetBit(int x, int p){
int m,y;
m = 1 << p ; // m = 1 << sizeof(int)
m = ~m;
y = x & m;
return y;
}

int resetBits(int x, int p, int n){

int m,y;
for(i = 0; i < n; i++)
x = resetBit(x,p-i);
}
 Efficient eResetBits(x,p,n)
p
eRresetBits(x, 6, 3)
31 30 29 28 9 8 7 6 5 4 3 2 1 0

0 1 0 0 … 0 1 0 1 1 1 1 0 1 1
x
31 30 29 28 9 8 7 6 5 4 3 2 1 0

m 1 1 1 1 … 1 1 1 0 0 0 1 1 1 1

x&m
 Efficient eResetBits(x,p,n)

int eResetBits(int x, int p, int n){

int m;
m = ~(~((~0) << n) << (p-n+1));
return x&m;
}
 invertBit(x,p)
Write down a function invertBit(x,p) that will invert a
bit of integer x at position p leaving other bits
unchanged. Assume 0 ≤ p ≤31
p

31 30 29 28 9 8 7 6 5 4 3 2 1 0

0 1 0 0 … 0 1 0 0 0 1 1 0 1 1
x

invertBit(x, 6)
 invertBit(x,p)
Write down a function setBit(x,p) that will invert a bit
of integer x at position p leaving other bits unchanged.
Assume 0 ≤ p ≤31
p

31 30 29 28 9 8 7 6 5 4 3 2 1 0

0 1 0 0 … 0 1 0 1 0 1 1 0 1 1
x

invertBit(x, 6)
a^0a
a ^ 1  ~a invertBit(x,p)
a^a0
Write down a function invertBit(x,p) that will invert a
bit of integer x at position p leaving other bits
unchanged. Assume 0 ≤ p ≤31

invertBit(x, 6) p

31 30 29 28 9 8 7 6 5 4 3 2 1 0

0 1 0 0 … 0 1 0 0 0 1 1 0 1 1
x

31 30 29 28 9 8 7 6 5 4 3 2 1 0

m 0 0 0 0 … 0 0 0 1 0 0 0 0 0 0
int invertBit(int x, int p){
int m,y;
m = 1 << p ; // m = 1 << sizeof(int)
y = x ^ m;
return y;
}
 invertBits(x,p,n)

Write down a function invertBits(x,p,n) that will invert

n bits of the integer x starting from position p leaving
other bits unchanged. Assume 0 ≤ p ≤31 and n ≤ p+1
p

31 30 29 28 9 8 7 6 5 4 3 2 1 0

0 1 0 0 … 0 1 0 0 0 1 1 0 1 1
x

invertBits(x, 6, 3)
 invertBits(x,p,n)

Write down a function invertBits(x,p,n) that will invert

n bits of the integer x starting from position p leaving
other bits unchanged. Assume 0 ≤ p ≤31 and n ≤ p+1
p

31 30 29 28 9 8 7 6 5 4 3 2 1 0

0 1 0 0 … 0 1 0 1 1 0 1 0 1 1
x

inverBits(x, 6, 3) Call invertBit(x,p)

in a loop
int invertBit(int x, int p){
int m,y;
m = 1 << p ; // m = 1 << sizeof(int)
y = x ^ m;
return y;
}

int invertBits(int x, int p, int n){

int m,y;
for(i = 0; i < n; i++)
x = invertBit(x,p-i);
}
 Efficient invertBits(x,p,n)
p
invertBits(x, 6, 3)
31 30 29 28 9 8 7 6 5 4 3 2 1 0

0 1 0 0 … 0 1 0 1 1 0 1 0 1 1
x
31 30 29 28 9 8 7 6 5 4 3 2 1 0

m 0 0 0 0 … 0 0 0 1 1 1 0 0 0 0

x^m
 Efficient eInvertBits(x,p,n)

int eInvertBits(int x, int p, int n){

int m;
m = ~(~0 << n) << (p-n+1);
return x^m;
}
RIGHT CIRCULAR SHIFT

int circularRightShift(int x){

unsigned int y = x;
int s = 8*sizeof(int);
return (y >> 1) | x << (s-1);

rightRotate (x, n)
 RIGHT CIRCULAR SHIFT
rightRotate (x, n)

int rightRotate (int x,int n){

unsigned y = x;
int s = 8*sizeof(int)-1;
return (~(~0 << n)& x) << (s-n+1) | (y >> n);
}
 xtractRightMostBits(x,n)

Write down a function xtractRightMostBits(x,n) that

will return rightmost n bits of the integer x.
Assume 1 ≤ n ≤32
n
xtractRightMostBits(x, 3)
31 30 29 28 9 8 7 6 5 4 3 2 1 0

0 1 0 0 … 0 1 0 0 0 1 1 0 1 1
x

31 30 29 28 9 8 7 6 5 4 3 2 1 0

0 0 0 0 … 0 0 0 0 0 0 0 0 1 1
 xtractRightMostBits(x,n)
xtractRightMostBits (x, n)

int xtractRightMostBits(int x, int n){

return ~(~0 << n)&x;
}