Reading: Binary Representation and Bitwise Operators

K&R 2.9, 6.9 ; Wright: A Tutorial on Binary Numbers.

Please submit a question by 9 p.m. on Monday, 14 February 2011.

I will come to your office hours to understand bits and etc.

You are not alone, so we'll use class time.

What is a 'bit' and what does it do?

Are we saying bits are just digits?

I really don't know what bits are, could you explain that for me?

Bits are binary digits. They provide the underlying representation for almost everything that can be stored on a computer

What does it mean to turn a bit on or off?

When we turn a bit on, we make it 1. When we turn a bit off, we make it 0.

Why do computers use binary?

It's fairly easy to represent 0's and 1's. For example, power is on is 1, and power is not on is 0.

Am I correct in stating that an 8-bit number is a number whose binary representation has 8 digits?

Yes.

I've only ever seen 8-bit and 16-bit numbers, so if a number's binary representation has 6 digits, is it just grouped as an 8-bit?

Well ... Remember that we allocate storage to variables, not to particular numbers. So, if we've allocated a char, then the number is stored in eight bits. If we've allocated an int, then the number is stored in thirty-two bits (at least on our machines).

Referring to the example

n = n & 0177

I am confused on how the last part (0177) sets to zero all but the low-order 7 bits of n. I am positive we went over the what the 0177 represents, I but i cannot remember how we did that. What does it mean by low-order?

The leading 0 means octal. So, each digit is is base 8. The octal 1 is a binary 001. The octal 7 is a binary 111. So the bits are in that number are 0...001111111. When we and a 0 bit with another bit, we get 0. When we and a 1 bit with another bit, we get that other bit. So the rightmost seven bits are preserved and the rest are set to 0. low-order effectively means rightmost.

How does one go about reading and using bitwise operators, such as x = x & ~077?

First you think about the underlying bits in each value. Then you apply the operator bit-by-bit. The example directly above might help.

Why is x=x & ~077 preferable to a 16-bit quantity such as x & 0177700? (pg.49)

Because ~077 works whether we're using 8 bits, 16 bits, 32 bits, or even 64 bits for our numbers. It's also shorter to type.

I don't understand what masking is. Can you explain it?

Masking is essentially the operation described above. We use the bitwise operators to mask off some bits, revealing only some. Why do we do this? It makes it easier to check the values of those bits.

What do you mean by & is often used to mask off some set of bits?

When you and 0 and any other bit, you get 0. Hence, we get rid of it (hide it behind a mask).

What does it mean when they say | is used to turn bits on?

When you or 1 and any other bit, you get 1. Hence, if we use | and 1's, we get 1.

Are bitwise operations really useful? I've never even heard mention of them before.... If so, then for what?"

What do we use bitwise operations for?

Most typically, for setting and getting particular bits in a number, as described above. Sometimes, to build more efficient mechanisms for computing. For example, to divide by 4, we can shift right 2 bits. We use them in MediaScheme to store the RGBA values. (R, G, B, and A are each 8 bits, so by shifting and or'ing, we can combine them into one 32-bit quantity.)

In the bit-fields part of the reading, why must the numbers be a power of two?

Because each bit in an integer represents a power of 2.

If I understand the reading correctly, bit-fields can be used to store information about identifiers within a function. Is this the only thing they are used for?

Yes, we typically use bit fields to store information on settings of various flags for a function or program.

Why would we use a bit-field instead of an array to store information. Is the only difference that bit-fields take up less memory?

The primary difference is that we save memory. The other is that we may be able to compute a bit more quickly with bit fields. (It's really fast to pass an integer around in the computer; it's much slower to pass around an array.)

I guess I'm still a little confused about how exactly bit-fields work and what their purpose is. Could you explain more where/how information in bit-fields is stored? Is a bit-field associated with a particular identifier in a function defined within the function? Are bit-fields created just when the function is complied, or every time the function is called?

I'll try to explain more about this.

Can we implement arithmetic with this underlying representation in class? Can we do it in a manageable way, so they aren't all just function calls?

Well, we're not going to build a computer, which is how many of these things are implement. However, we can talk a little about it.

Is there a subtraction operation for binary numbers?

Most often, we negate and add.

The reading doesn't explain binary division very well.

It's been awhile since I implemented binary division. In the general case, I think you do it like long division. But for divisors that are powers of two, it's easy: You can just shift the bits. We'll do an example in class.

Could you explain the difference between bitwise operators and logical operators?

Bitwise operators deal a bit at a time. So, we convert to bit notation, and look at each pair of bits. Logical operators simply look to see whether something is false (0) or true (non-zero). Here's one example: both 5 (101) and 2 (010) are considered true. If we combine them with &&, we get something that's true (probably 1). If we combine them with &, we get 0.

Can you explain Excess 2^(m-1) and two's complement? Why are these needed as opposed to just normal signed or unsigned numbers?

What's the practical use of two's complement? (Sorry I'm late!)

We will cover these questions in class.

We learned about one's complement and two's complement, but are there things like 9's complement?

Not that I know of. The four representations we covered are the primary ones that are used in practice. (There are other excess notations.)

I found the section in the Binary Tutorial on One's Complement confusing. It description of -12's representation in binary seems to conflict with the representation mentioned directly above.

This question is vague, since there are four representations. I'll try to go over them in class.

Could you re-explain pointers and arrays and basically all of 5.9?

5.9 wasn't assigned. 6.9 was. So, no.

Do our machines assign fields left to right or right to left?

I never remember. We can conduct an experiment to check.