Bit Operations/Optimization

Question 1

List 4 types of programs that need to perform operations at the bit level:

Answer 1

1. Systems programs(including compilers and OS’s)
2. Encryption programs
3. Graphics programs
4. Programs for which fast execution and/pr efficient use of space is critical

Question 2

What are the bitwise shift operators and how do they work?

Answer 2

• << left shift
  
  • for each bit that is “shifted off” the left end of i, a zero bit enters at the right
• >> right shift
  
  • if the value shifted is nonnegative, zeros are added at the left as needed

(may be of any integar type, including char)

Question 3

unsigned short i, j;

What would the result(in binary) be of the following operations:

1. i = 13;
2. j = i << 2;
3. j = 1 >> 2;

Answer 3

1. 0000000000001101
2. 0000000000110100
3. 0000000000000011

Question 4

How do you read binary numbers (what’s the basic formula as compared to base 10)?

Represent 16, 7 and 21 in binary

Answer 4

In general, it is powers of 2, starting from the right at 2^0 + 2^1, etc. This is the same way our base ten math work. 21 = 1 X 10^0 + 2 * 10^1

16 in binary = 0000000000010000

7 in binary = 0000000000000111

21 in binary = 0000000000010101

Question 5

What is the binary representation of the following:

1. i = 13;
2. i <<= 2;
3. i >>= 2;

Answer 5

1. 0000000000001101
2. 0000000000110100
3. 0000000000001101

Question 6

What is the precedence (order/priorty) or a bitwise shift operator?

What does i << 2 + 1 mean?

Answer 6

It is lower than arithmatic.

it means i << 3

Question 7

What are the bitwise “compliment”, “and”, “exclusive or” and “inclusive or” operators? In general, what do they do?

Answer 7

• ~ = compliment (switches bits from what they were, e.g. 0 to 1
• & = and (works like a regular and statment, is true if bits are both 1)
• | = inclusive or (works like a regular or, if one of the items is 1/true then the statement is 1/true)
• ^ = exclusive or (if the bit is set and are different then it sets it to true, if the bits are the same, then it sets it to false)

Question 8

unsigned short, i, j, k;

What affect would the following operations have in binary?

1. i = 21;
2. j = 56;
3. k = ~i;
4. k = i & j;
5. k = i ^ j;
6. k = i | j;

Answer 8

1. 0000000000010101
2. 0000000000111000
3. 1111111111101010
4. 0000000000010000
5. 0000000000101101
6. 0000000000111101

Question 9

Evaluate the following using binary.

1. i = 21;
2. j = 56;
3. i &= j;
4. i ^= j;
5. i |= j;

Answer 9

1. 0000000000010101
2. 0000000000111000
3. 0000000000010000
4. 0000000000101000
5. 0000000000111000

Question 10

In general how do hexadecimal numbers work?

What is the number 1BC?

Answer 10

Hex numbers are 16 bits, 0-9 + A-F

0-9 is obviously 0-9 and A - F is 10-15

1BC in hex is 444

Question 11

1. How does C know we are using hex numbers?
2. How do you print in hex format with printf?
   
   1. how to print min of 4 digits?
3. How many bits is each hex number represented by?

Answer 11

1. hex numbers in C are prefixed by 0x (captilization does not matter)
2. %x
   
   1. %04x
3. hex numbers are represented by 4 bits (2⁴ = 16)

Question 12

What is Binary Code Decimal (BCD). Provide the example for the following:

1. 3
2. 4
3. 7
4. B

Answer 12

The 4 bit representation of the decimal digit

1. 0011
2. 0100
3. 0111
4. 1011

Question 13

In general, how does it work to use bitwise operators to access bits?

1. What is the easiest way to set bit 4 of i?
2. How would i |= 1 << j be equivalent?
3. if j has a value of 3, what would 1 << j be in hex and binary?

Answer 13

The easiest way to set bit 4 of i is to use to or the value of i with the hex constant 0x0010:

1. i = 0x0000; // this is 0 in hex
   
   • 00000000000000000
2. i |= 0x0010; //this is 16 in hex
   
   • 00000000000010000 (this is 16 in hex now)
3. hex = 0x008, binary 0000000000001000

Question 14

If we wanted to clear bit 4 of i how would that be done?

i = 0x00ff;

Answer 14

We would need a number whose only different bit is in the 5th position and use the & operator.

i in binary is 00000000111111111

i &= 0x0010 (16)

in binary is 0000000011101111 (and flipping the only different bit, bit 4 (in the 5th position)

Question 15

1. In general, how do you test a bit?
2. How would you test if bit 4 is set?
3. How would you test if bit j is set?
   4.

Answer 15

1. Using an if statement the & operator and a specific number corresponding to the specific bit to test.
2. if ( i & 0x0010)
3. if ( i & 1 << j )

Question 16

What is a bit-field and in general how is it used?

Answer 16

a bit-field is used in a struct, it allows you to set the specific number of bits you want to use to store a value. You would use this when working with direct bits would take up less space than the actual integer values.

Example:

struct exampleStruct{

unsigned int day: 5; //set aside 5 bits

};

In the example above, day can have up to 31 values (2⁴+2³+2²+2¹+2⁰ as each 2 represents 1 bit)

Question 17

What would the following line output?:

unsigned int i = 0X11;

unsigned int j = 0x32F;

printf(“%d %x %04x\n”, i, i, i);

printf(“%d”, j);

Answer 17

17 11 0011

815