Bit Operations

Question 1

Looking Inside a Value

Answer 1

• Internally, int and double values are represented with bit patterns
• A good programming language lets us ignore details of how this is done
  – We can think of an int as … well, an integer
• But, sometimes we want to work with individual bits in a value … why?
  – Maybe we could pack more values into limited memory.
  – Maybe we need to talk to hardware or work with a file format that requires particular bit patterns
  – Maybe we need to perform compression or encryption
  – Maybe we can better exploit bit-level parallelism in the hardware

Question 2

Application : UTF-8 Encoding

Answer 2

• UTF-8 is a file format for non-ASCII text.
  – A character code can be up to 21 bits.
  – It uses just some bits from each byte.
• A character with a 7-bit code uses just one byte.
  0b6b5b4b3b2b1b0
  00000000000000b6b5b4b3b2b1b0
• An 11-bit code is spread across two bytes.
  110b10b9b8b7b6 10b5b4b3b2b1b0
  0000000000b10b9b8b7b6b5b4b3b2b1b0
  We need to be able to extract these bits and put them together.

Question 3

Working with Bits

Answer 3

• C99 provides no standard way to …
  – … give a literal constant in binary
  i = 011001011;
  – … read an integer as a string of binary digits
  scanf( “%b”, &i );
  – … print a value as a string of binary digits
  printf( “%b”, i );
• What can we do?
  – Use octal or hexadecimal
  – Write our own code to work at the bit level.

Question 4

Hexadecimal Review

Answer 4

0 0000
1 0001
2 0010
3 0011
4 0100
5 0101
6 0110
7 0111
8 1000
9 1001
A 1010
B 1011
C 1100
D 1101
E 1110
F 1111

Question 5

C Bit-Level Operators

Answer 5

• We have some operators just for manipulating
  values at the bit level
  ++ – Postincrement, postdecrement
  ++ – Preincrement, predecrement
  + - unary positive, negative
  ! logical not
  ~ bitwise complement
  (type) type cast
  sizeof sizeof operator
• / % Multiply, divide, mod
  + - Add, subtract
  «_space;» Bitwise left and right shift
  < <= > >= Relational Operators
  == != Equals, not equals
  & Bitwise and
  ^ Bitwise exclusive or
  | Bitwise (inclusive) or
  && Logical and
  || Logical or
  ? : Ternary operator
  = += -= *= … Assignment, and its friends
  , Comma operator

Question 6

Looking at Bits

Answer 6

• Signed-ness matters
  – The same pattern of bits can look different as a signed or an unsigned value.
  unsigned char x;
  signed char y;
  x = 0xA9; // binary 10101001 (that means 169)
  y = 0xA9; // binary 10101001 (here, that’s -87)
  printf( “%d\n”, x ); -> These get converted
  to int when passed to printf. This will print 169
  printf( “%d\n”, y ); -> This will print -87
• Width matters
  – Signed values will be sign-extended when converted to a wider type.
  – Remember, C promotes to int / unsigned int for any arithmetic operation.
  unsigned char x;
  signed char y;
  x = 0xA9; // binary 10101001 (A9)
  y = 0xA9; // binary 10101001 (A9)
  printf( “%X\n”, x ); -> Prints A9
  printf( “%X\n”, y ); -> Prints FFFFFFA9(sign extension)

Question 7

Meet ~ (a Unary Bitwise Operator)

Answer 7

• Unary operator ~ is a bitwise complement
  unsigned char x, y;
  x = 0x1A; // binary 00011010
  y = ~x; // binary 11100101
  printf( “%X\n”, y ); -> This will print E5, like you
  expect.
  printf( “%X\n”, ~x ); -> This will print FFFFFFE5
  x is expanded to an int before the complement is performed.

Question 8

Friends of ~

Answer 8

• We have three different “not” operators.
• They each do slightly different job.
  signed char x, y, z, w;
  x = 0x1A; // binary 00011010
  y = ~x; // binary 11100101 -> I flip all the bits
  z = !x; // binary 00000000 -> I swap true<–>false
  w = -x; // binary 11100110 -> I perform the two’s complement operation

Question 9

Binary Bitwise Operators

Answer 9

• The next three operators are binary, they take two operands
  – & is a a bitwise and a 1 in the result only if both corresponding input bits 1
  – ^ is bitwise exclusive or a 1 in the result only if both corresponding input bits
  are different
  – | is bitwise (inclusive) or
  a 1 in the result if either of the corresponding input bits are 1

Question 10

Bitwise And

Answer 10

• Here’s how bitwise and (&) works:
  0 & 0 = 0
  0 & 1 = 0
  1 & 0 = 0
  1 & 1 = 1
  Written as a single (infix)
  ampersand.
  I can combine multiple
  bits at the same time.
• Logical and is different; it interprets each input value as a single truth value.
  1 1 0 0 1 0 1 0
  && 1 0 1 0 0 1 1 0
  ——————
  0 0 0 0 0 0 0 1 -> true

Question 11

Bitwise Or

Answer 11

• Bitwise Or is similar
• It computes each bit of the result based on
  corresponding bits of the operands.
  1 | 1 = 1
  1 | 0 = 0
  0 | 1 = 1
  0 | 0 = 0
• Logical or is like this, but it considers each
  input to be one big truth value.
  1 1 0 0 1 0 1 0
  || 1 0 1 0 0 1 1 0
  ——————
  0 0 0 0 0 0 0 1

Question 12

Bitwise vs Logic Operators

Answer 12

• Bitwise And and Or don’t care about short
  circuiting.
  D = A & ( B | C ); -> I still get evaluated even if A
  is zero.
• Corresponding logical operators are
  guaranteed to short circuit.
  D = A && ( B || C ); ->I won’t get evaluated unless A is true (non-zero).

Question 13

Exclusive Or

Answer 13

• One more bitwise operator, exclusive Or.
  1 1 0 0 1 0 1 0
  & 1 0 1 0 0 1 1 0
  —————–
  1 0 0 0 0 0 1 0
  1 1 0 0 1 0 1 0
  | 1 0 1 0 0 1 1 0
  —————–
  1 1 1 0 1 1 1 0
  if bits are different, true is 1
  false is 0
  1 1 0 0 1 0 1 0
  ^ 1 0 1 0 0 1 1 0
  —————–
  0 1 1 0 1 10 0

Question 14

Shift Operators(Left)

Answer 14

• Left logical shift of x by y bits: x «_space;y
  – For example: 0x1A «_space;5
  0 0 0 1 1 0 1 0
  0 0 0 1 1 0 1 0 0 0 0 0 0
  New zeros shifted in on this end. If you shift far enough, you can lose bits off the high end.
  – Operands should be integer types
  – If x has n bits, y should be between 0 and n-1
  – You can’t left shift by a negative amount, but …

Question 15

Shift Operators(Right)

Answer 15

• Right logical shift of x by y bits: x»_space; y
  – For example: 0xCA»_space; 2
  1 1 0 0 1 0 1 0
  0 0 1 1 0 0 1 0
  You get new high order zeros shifted in on the
  left.
  bits shifted past the low-order bit are discarded.
  – Again, operands should be integer types
  – If x has n bits, y should be between 0 and n-1
  – Really, what gets shifted in on the left depends ….
  makes sense for unsigned

Question 16

Shift Operators(Right Arithmetic)

Answer 16

• Right arithmetic shift of x by y bits: x»_space; y
  – Wait! This is the same operator.
  – Behavior depends on whether the left operand is signed.
  1 1 0 0 1 0 1 0
  1 1 1 1 0 0 1 0

0 1 0 0 1 0 1 0
0 0 0 1 0 0 1 0
For signed operands, you get
copies of the high-order bit shifted in.
* Why arithmetic shift?
– For signed values, this maintains the sign.
* We can use left shift to multiply by 2 or any
power of 2
– x «_space;y is the same as x * 2^y
* And, we can use right shift like a divide operation
– x»_space; y is the same as x / 2^y -> But, this only
works for positive numbers.
unsigned int x y;
x = 75 «_space;2; // that’s 300
y = 75»_space; 2; // that’s 18

Makes sense for signed
No left arithmetic operators

Question 17

OK, How Do We Use These Operators?

Answer 17

• What can we do with these operators?
• Lots of useful things:
  – Clear selected bits to zero or set them to 1
  – Test if selected bits are zero or 1
  – Loop through individual bits.
  – Copy selected bits from x to y or to another
  position in x
  – Access a bit field as if it was a tiny integer

Question 18

Clearing Selected Bits

Answer 18

• We can think of the & operator as applying a
  mask
  0 1 1 0 1 1 0 0
  & 1 1 0 0 1 0 1 0
  —————–
  0 1 0 0 1 0 0 0
• Wherever we have a 0 in the mask, a bit is
  cleared
• Wherever we have a 1, the original value
  passes through
• So, we could clear just the low-order 4 bits
  unsigned char x;
  x = 0xD3; // binary 11010011
  x = x & 0xF0; // mask 11110000
  // now 11010000
  x = 0xD3; // binary 11010011
  x &= 0x55; // mask 01010101
  // now 01010001
  Or, we could clear every other bit
  &= -> We also have these for bitwise
  operators.

Question 19

Setting Selected Bits

Answer 19

• Again, it’s just how you think about the bitwise operators
• We can think of | as applying a different kind of mask
  0 1 1 0 1 1 0 0 -> I’m the value you want
  to work with.
  | 1 1 0 0 1 0 1 0 -> I say what bits to set and
  which ones remain the same.
  —————–
  1 1 1 0 1 1 1 0
• Wherever we have a 1, a bit is set (made 1)
• Wherever we have a 0, the original value passes through
• So, we could set just the low-order 4 bits
• Or, we could set just the first and last.
  unsigned char x;
  x = 0xD3; // binary 11010011
  x = x | 0x0F; // mask 00001111
  // now 11011111
  x = 0xD6; // binary 11010110
  x |= 0x81; // mask 10000001
  // now 11010111

Question 20

Inverting Selected Bits

Answer 20

• With the ^ operator, a 1 in the mask says
  where to flip a bit
  0 1 1 0 1 1 0 0 -> I’m the value you want
  to work with.
  ^ 1 1 0 0 1 0 1 0 -> I say what bits to change
  —————–
  1 0 1 0 0 1 1 0
• We could use this to flip just the low-order bit
  unsigned char x;
  x = 0xD3; // binary 11010011
  x ^= 0x01; // mask 00000001
  // now 11010010

Question 21

Testing Selected Bits

Answer 21

• First, use & to mask off the bits you don’t want.
  0 1 1 0 1 1 0 0
  & 0 0 0 0 1 1 1 1
  —————–
  0 0 0 0 1 1 0 0
• Then what?
  – If the result is zero, none of those bits were 1
  – If the result matches the mask, they were all 1
  unsigned char x, mask;
  x = 0x6C; // binary 01101100
  mask = 0x0F; // mask 00001111
  if ( ( x & mask ) != 0 ) // 00001100 != 00000000
  …;
  if ( ( x & mask ) == mask ) // result 00001100 == 00001111
  …;
  Carefule about precedence = comes before & or I

Question 22

Counting or Printing

Answer 22

• So, if we can build a mask, we can get to any bits
  we want.
• What if we want to be able to access every bit …
  individually.
  – Say, we want to iterate over the bits in an int.
• We can build a movable mask for this
  – 0x01 «_space;i is a mask with a 1 just in bit position i
  – And, of course, ~(0x01 «_space;i) is the
  complementary mask

Question 23

Counting Bits

Answer 23

• We can iterate over the bits, then apply the
  mask to check each one.
  unsigned int secret = 2348291;
  int bcount = 0;
  for ( int i = 0; i < 8 * sizeof( int ); i++ ) {
  if ( secret & ( 1 «_space;i ) )
  bcount++;
  }
  printf( “That’s %d one bits\n”, bcount );
• We could use the same technique to print a
  number in binary

Question 24

Copying Selected Bits

Answer 24

• Say we wanted to copy the middle four bits in a character
• In the source, we can use & to mask off everything but the bits we
  want to copy.
• In the destination, we can use & with a complementary mask to
  clear out these bits
• Then, we can use | to turn on just the bits copied from the source
  Source:
  1 0 1 0 1 1 0 1
  & 0 0 1 1 1 1 0 0
  —————–
  0 0 1 0 1 1 0 0
  Destination
  0 1 0 0 1 1 1 1
  & 1 1 0 0 0 0 1 1
  —————–
  0 1 0 0 0 0 1 1

Result:
0 1 0 0 0 0 1 1
| 0 0 1 0 1 1 0 0
—————–
0 1 1 0 1 1 1 1

Question 25

Bit Fields

Answer 25

* We can pack multiple small integer values into a variable. – This can save some storage or reduce communication overhead. – It can even let us manipulate multiple values in parallel. There could be 4 values stored in 1 32 bit int

Question 26

Extracting a Bit Field

Answer 26

* To extract a particular field: – Mask off the other bits – Then, shift down (so you can use the contents of the field like an int) – Say, we want to get just the middle 4 bits of a char. 1 0 1 0 1 1 0 1 & 0 0 1 1 1 1 0 0 ----------------- 0 0 1 0 1 1 0 0 0 0 1 0 1 1 0 0 >> 2 ------------------ 1 0 1 1

Question 27

Changing a Bit Field

Answer 27

* Then, we can manipulate the value of that field. * And put the result back when we’re done. 1 0 1 1 + 1 ->Add one to the field. ----------------- 1 1 0 0 << 2 -> Shift it back to where it goes ----------------- 1 1 0 0 0 0 & 0 0 1 1 1 1 0 0 -> Mask off other bits (in case ofoverflow) ----------------- 0 0 1 1 0 0 0 0 Original char make room for new field value 1 0 1 0 1 1 0 1 & 1 1 0 0 0 0 1 1 ----------------- 1 0 0 0 0 0 0 1 Insert the updated value 1 0 0 0 0 0 0 1 | 0 0 1 1 0 0 0 0 ----------------- 1 0 1 1 0 0 0 1

Question 28

Bit Fields in Structs

Answer 28

* Inside a struct, we can use integer fields with variable numbers of bits – The compiler will worry about packing/unpacking them in words of memory. * Why would we want this? – We could save memory, if we need several fields for small integer values – Maybe we could match the binary format of some file – … or the format for communicating with some hardware device

Question 29

Using Bit Fields

Answer 29

* Normally, fields occupy consecutive groups of whole bytes, maybe even with some padding. * Internally, bit fields can use parts of individual bytes. typedef struct { unsigned short red; unsigned short green; unsigned char blue; unsigned char alpha; } RegularColor; The compiler says “6 Bytes” typedef struct { unsigned int red:9; unsigned int green:9; unsigned int blue:6; unsigned int alpha:6; } PackedColor; But here just 4. Does not stop at byte boundary * Mostly, you can use bit fields like any other integer field. PackedColor c1 = { 511, 256, 0, 32 }; -> Initialize them. int r = c1.green; -> Read them c1.blue += 16; -> assign and change them c1.red++; -> overflow them * But, you can’t take their addresses. A bit field may start inside a byte. -> void *ptr = &( c1.red );

Question 30

Wait Just a Minute!

Answer 30

* Didn’t we just learn how to do bit fields, with bitwise operators! * Was that a waste of time? – Yes … I mean No. * For bit fields in a struct, the compiler determines the layout. – So code that depended on a particular packing of the bits wouldn’t be portable. – And if we really wanted to use a file format or talk to hardware with bit fields in a particular format … – … we’d probably have to write that code ourselves * So, are bit fields in a struct useful? * Yes – They can reduce the memory footprint of your program. – They can give you convenient access to bit fields in a file, if portability isn’t important for your application.