# bit shifting

tyler jones

Ranch Hand

Posts: 101

posted 16 years ago

I'm trying to learn more about shifting bits and using the binary AND, OR, AND XOR operators. I've been thinking on a way to quiz myself to learn how to use these would be to just write down a bunch of numbers like 0110, 0111, 0101 and so forth, and then write a program that would use the binary operators on them. But before running the program, I would try to figure them out for myself. Then run the program and see if I was right. Here's my problem though....how do I figure out the binary value of the number 3? or 4? Basically, just so that I know when I get a value of 0110, I know what number that is and then when I run the program, I'll know whether I was right or not. I hope this made sense. Thanks a lot!

posted 16 years ago

Hi Tyler -

This is nothing more than a trick to learn. Think of the decimal system as being built on powers of 10. We have a ones place, a tens place, a hundreds place, and so. We also have ten values for each position, 0-9.

In binary, we only have two values per position, 0 and 1. The binary system is built on powers of two. So instead of ones, tens, hundreds, etc., we have ones, twos, fours, eights, sixteens, and so on.

The trick comes in breaking down decimal numbers into binary form. Let's take a fun one, like 57. In decimal we have 5 tens, 7 ones. In binary we have 1 thirty-two, 1 sixteen, 1 eight, no fours, no twos, and 1 one, or 111001.

It takes some getting used to, and practice is the key. You'll get the hang of it before long.

-----------------

Michael Ernest, co-author of: The Complete Java 2 Certification Study Guide

[This message has been edited by Michael Ernest (edited December 30, 2000).]

This is nothing more than a trick to learn. Think of the decimal system as being built on powers of 10. We have a ones place, a tens place, a hundreds place, and so. We also have ten values for each position, 0-9.

In binary, we only have two values per position, 0 and 1. The binary system is built on powers of two. So instead of ones, tens, hundreds, etc., we have ones, twos, fours, eights, sixteens, and so on.

The trick comes in breaking down decimal numbers into binary form. Let's take a fun one, like 57. In decimal we have 5 tens, 7 ones. In binary we have 1 thirty-two, 1 sixteen, 1 eight, no fours, no twos, and 1 one, or 111001.

It takes some getting used to, and practice is the key. You'll get the hang of it before long.

-----------------

Michael Ernest, co-author of: The Complete Java 2 Certification Study Guide

[This message has been edited by Michael Ernest (edited December 30, 2000).]

*Make visible what, without you, might perhaps never have been seen.*

- Robert Bresson

tyler jones

Ranch Hand

Posts: 101

posted 16 years ago

I think I understand your answer, but let me make sure. Okay, if I have the number 87, would it have 1 64, 1 16, 0 8, 1 4, 1 2, 1 1? So it would be 110111? At what point does it quit compounding? I mean, does it go 64, 128 to infinity? Or does it stop somewhere? Thanks for your explanation. I'm sure it's getting me going in the right direction.

Allen Alchian

Ranch Hand

Posts: 83

posted 16 years ago

Tyler,

You've got the hang of it. Now, I guess I'll answer your last question.

The numbers continue until you run out of bits. For example, if you have only 2 bits with which to count, then you have 4 different numbers at your disposal (calculated by multiplying 2*2 in this case).

Likewise if you have eight bits to play with (8 bits = 1 byte), then you have 256 different numbers available. (multiply 2*2*2*2*2*2*2*2 = 256)

If you have 16 bits at your disposal, then you can create 65,536 different numbers. (Incidentally, this is why the old DOS operating system, which was a 16 bit file system, was limited to storing a maximum of 65,536 files on a hard drive).

Java uses 32 bits to represent its integer values. I'll let you calculate how many different numbers that can represent. But remember, half of them are negative numbers, so the highest integer value allowable is half what you might expect (31 bits are to represent numbers and one bit to represent the sign...called the "sign bit".)

Hope this helps. Probably raised more questions than I answered!

Allen

You've got the hang of it. Now, I guess I'll answer your last question.

The numbers continue until you run out of bits. For example, if you have only 2 bits with which to count, then you have 4 different numbers at your disposal (calculated by multiplying 2*2 in this case).

Likewise if you have eight bits to play with (8 bits = 1 byte), then you have 256 different numbers available. (multiply 2*2*2*2*2*2*2*2 = 256)

If you have 16 bits at your disposal, then you can create 65,536 different numbers. (Incidentally, this is why the old DOS operating system, which was a 16 bit file system, was limited to storing a maximum of 65,536 files on a hard drive).

Java uses 32 bits to represent its integer values. I'll let you calculate how many different numbers that can represent. But remember, half of them are negative numbers, so the highest integer value allowable is half what you might expect (31 bits are to represent numbers and one bit to represent the sign...called the "sign bit".)

Hope this helps. Probably raised more questions than I answered!

Allen

Allen

tyler jones

Ranch Hand

Posts: 101

Allen Alchian

Ranch Hand

Posts: 83

posted 16 years ago

Yes, that is essentially correct; the highest order bit (left-most) is the sign bit when you are expressing negative numbers.

But

0000 0000 0000 0000 0000 0000 0000 0001

...that a negative one is simply...

1000 0000 0000 0000 0000 0000 0000 0001

It doesn't work that way. (You knew it was too good to be true.) Instead, a method called "two's compliment" is used to compute the binary code of a negative number, and -1 comes out to be represented as (hang on to your byte)...

1111 1111 1111 1111 1111 1111 1111 1111

Now I'll bet you're sorry you asked.

But

*don't*assume that because the value of one is expressed in binary as...0000 0000 0000 0000 0000 0000 0000 0001

...that a negative one is simply...

1000 0000 0000 0000 0000 0000 0000 0001

It doesn't work that way. (You knew it was too good to be true.) Instead, a method called "two's compliment" is used to compute the binary code of a negative number, and -1 comes out to be represented as (hang on to your byte)...

1111 1111 1111 1111 1111 1111 1111 1111

Now I'll bet you're sorry you asked.

Allen

tyler jones

Ranch Hand

Posts: 101

posted 16 years ago

Whoah! Now hold on a second. I read in two of my books that by changing the most signifigant bit which is the last on the left from a zero to a one, that it did change it from a positive to a negative number. So are you saying that I have to in fact change all zeros to ones, not just the last one?

Allen Alchian

Ranch Hand

Posts: 83

posted 16 years ago

No, I didn't say you have to change all zeros to ones to get a negative number. (It happened that way in the previous example I used.)

Your books are correct that by changing the most significant bit to one you get a negative number...but you don't get the negative number you expected. To change a positive number in bit notation, to its negative equivalent, Java (like most popular languages) uses the process called "twos complement." Look in the index of your books for "twos complement" if you want to know the algorithm...it's not terribly difficult, but it's not something I make a point of remembering. If you need to know the process and can't find it in a book, let me know and I'll dig it out for you.

Your books are correct that by changing the most significant bit to one you get a negative number...but you don't get the negative number you expected. To change a positive number in bit notation, to its negative equivalent, Java (like most popular languages) uses the process called "twos complement." Look in the index of your books for "twos complement" if you want to know the algorithm...it's not terribly difficult, but it's not something I make a point of remembering. If you need to know the process and can't find it in a book, let me know and I'll dig it out for you.

Allen