# bit shifting

Christophe Lee

Ranch Hand

Posts: 142

posted 14 years ago

Hi guys,

I am having trouble understanding negative bit representations. I understand the two's complement thing and understand how shifting works and also understand the bitwise operators....except when it comes to negative numbers.

I thought an int -1 would be something like this:

1000 0000 0000 0000 0000 0000 0000 0001

But instead, it's:

1111 1111 1111 1111 1111 1111 1111 1111

I thought the sign bit was the left most bit, so if the left most bit was a 1, then the number is negative. But it seems to be more complicated than that.

Thanks for your explanations.

I am having trouble understanding negative bit representations. I understand the two's complement thing and understand how shifting works and also understand the bitwise operators....except when it comes to negative numbers.

I thought an int -1 would be something like this:

1000 0000 0000 0000 0000 0000 0000 0001

But instead, it's:

1111 1111 1111 1111 1111 1111 1111 1111

I thought the sign bit was the left most bit, so if the left most bit was a 1, then the number is negative. But it seems to be more complicated than that.

Thanks for your explanations.

Dave Vick

Ranch Hand

Posts: 3244

posted 14 years ago

I think you mean the bit on the right, the low order bit.

Just to illustrate all the steps for christophe

to convert -21 to binary

hope that might make it easier to follow.

Another source you might want to check out is http://www.javaranch.com/campfire/StoryBits.jsp

Dave

[This message has been edited by Dave Vick (edited July 23, 2001).]

Originally posted by Snylt Master:

Hi Christophe!

To get this to -21 You use 2 complement.

flip all bit and add 1 to the first bit. That's the bit to the left.

I think you mean the bit on the right, the low order bit.

Just to illustrate all the steps for christophe

to convert -21 to binary

hope that might make it easier to follow.

Another source you might want to check out is http://www.javaranch.com/campfire/StoryBits.jsp

Dave

[This message has been edited by Dave Vick (edited July 23, 2001).]

Dave

Snylt Master

Ranch Hand

Posts: 55

posted 14 years ago

Sorry. I've deleted my post because I thought I couldn't explain it the way it shold be explained.

Here is my original post.

Hi Christophe!

If you have a number say 21 then the bit pattern will be.

00000000 00000000 00000000 00010101

To get this to -21 You use 2 complement.

flip all bit and add 1 to the first bit. That's the bit to the right.

11111111 11111111 11111111 11101011

It is difficult to figure out what the -21 pattern represents. So if you have -45 in an bitpattern

11111111 11111111 11111111 11010011

To know what this bitpattern is you just flip it and add one

00000000 00000000 00000000 00101101 -- this is 45

Hope you get what I meen. It's difficult to see the negative bit pattern but if you use 2 complement to make it posistive you can figure out what the negative pattern is in a positive value.

Here is my original post.

Hi Christophe!

If you have a number say 21 then the bit pattern will be.

00000000 00000000 00000000 00010101

To get this to -21 You use 2 complement.

flip all bit and add 1 to the first bit. That's the bit to the right.

11111111 11111111 11111111 11101011

It is difficult to figure out what the -21 pattern represents. So if you have -45 in an bitpattern

11111111 11111111 11111111 11010011

To know what this bitpattern is you just flip it and add one

00000000 00000000 00000000 00101101 -- this is 45

Hope you get what I meen. It's difficult to see the negative bit pattern but if you use 2 complement to make it posistive you can figure out what the negative pattern is in a positive value.

Preparing for the Java 2 Certification exam

Christophe Lee

Ranch Hand

Posts: 142

posted 14 years ago

Ok, I didn't know that!

So, -4 would be:

step 1.) 0000 0010 //byte 4

step 2.) 1111 1101 //flip

step 3.) 1111 1100 //add 1, the right most bit changes to 0

so -4 is:

1111 1100 //right?

ps: I'm assuming on step 3 that when you add 1 to 1 the result is 0 because otherwise you can't change -4 back to 4 with the same logic.

So, -4 would be:

step 1.) 0000 0010 //byte 4

step 2.) 1111 1101 //flip

step 3.) 1111 1100 //add 1, the right most bit changes to 0

so -4 is:

1111 1100 //right?

ps: I'm assuming on step 3 that when you add 1 to 1 the result is 0 because otherwise you can't change -4 back to 4 with the same logic.

Dave Vick

Ranch Hand

Posts: 3244

posted 14 years ago

You have the concept right, except for 2 things:

4 in binary is

00000000 00000000 00000000 0000100

so flipping the bits is:

11111111 11111111 11111111 1111011

then you add one and the result is

11111111 11111111 11111111 1111100

the reason you got the right answer is because when you add one to a one you have to carry over to the next highest bit until you reach a zero which would become a one. You didnt do this in your answer, if you did your answer would have been wrong.

The only other thing you should remember to do is always write the entire integer out, use all 32 bits. It will save you a lot of heartache when you apply the unsigned right shift operator to negative numbers. Try this using just 8 bits then try with all 32 and you'll see what I mean:

-5 >>> 2

(answer is here: http://chipvick.earthisp.net/comp/scjpStudy.html#bitops )

hope that helps

Dave

[This message has been edited by Dave Vick (edited July 23, 2001).]

4 in binary is

00000000 00000000 00000000 0000100

so flipping the bits is:

11111111 11111111 11111111 1111011

then you add one and the result is

11111111 11111111 11111111 1111100

the reason you got the right answer is because when you add one to a one you have to carry over to the next highest bit until you reach a zero which would become a one. You didnt do this in your answer, if you did your answer would have been wrong.

The only other thing you should remember to do is always write the entire integer out, use all 32 bits. It will save you a lot of heartache when you apply the unsigned right shift operator to negative numbers. Try this using just 8 bits then try with all 32 and you'll see what I mean:

-5 >>> 2

(answer is here: http://chipvick.earthisp.net/comp/scjpStudy.html#bitops )

hope that helps

Dave

[This message has been edited by Dave Vick (edited July 23, 2001).]

Dave

Snylt Master

Ranch Hand

Posts: 55

Dave Vick

Ranch Hand

Posts: 3244

posted 14 years ago

Snylt

Adding one to the right (lowest order) bit is the same as adding 1. The reason I contradicted you is because in your original post you said add it to the lefthand bit - that would just change the sign.

For the question you just posted...

The number you gave is 6 in binary this is:

I used the code tag because it keeps everything lined up so you can see the alignment.

when you add the one to the 11111111 11111111 11111111 1111001 the bit on the far right becomes a 0, but then you have to carry the one to the next bit on the left. Becauise it is a 0 it becomes a 1 and no further carrying is needed.

hope that helps

Dave

[This message has been edited by Dave Vick (edited July 23, 2001).]

Adding one to the right (lowest order) bit is the same as adding 1. The reason I contradicted you is because in your original post you said add it to the lefthand bit - that would just change the sign.

For the question you just posted...

The number you gave is 6 in binary this is:

I used the code tag because it keeps everything lined up so you can see the alignment.

when you add the one to the 11111111 11111111 11111111 1111001 the bit on the far right becomes a 0, but then you have to carry the one to the next bit on the left. Becauise it is a 0 it becomes a 1 and no further carrying is needed.

hope that helps

Dave

[This message has been edited by Dave Vick (edited July 23, 2001).]

Dave

Snylt Master

Ranch Hand

Posts: 55

posted 14 years ago

I'm sorry Dave... now I'm really confused.

I understand the flip but when adding one why must the bit

next to the added bit become 1? Why isn't it still 0?

Please help!

[This message has been edited by Snylt Master (edited July 24, 2001).]

I understand the flip but when adding one why must the bit

next to the added bit become 1? Why isn't it still 0?

Please help!

[This message has been edited by Snylt Master (edited July 24, 2001).]

Preparing for the Java 2 Certification exam

Dave Vick

Ranch Hand

Posts: 3244

posted 14 years ago

You have to carry the one.

here is a basic example 1 + 1 = 2

When you add 1 to 1 the bit will change to 0 but then you have to carry the 1 to next highest bit. It is the same as adding 9 + 1. In base 10 numbers the highest digit is a 9, anytime you add to the 9 you start over at the beginning and increment the next most significant digit.

19

+ 1

the 9 becomes a zero and you carry the one to the left and add it to the digit there, in this case it becomes a two, so the answer is 20. If it would have been a nine also then it would have started over at zero and the 1 would have carried to the left again until it found a digit it could be added to that didn't exceed nine. Binary works the exact same way.

look at 12 + 4

starting at the right we add the two together, the first two digits are 0 + 0 so they are both 0. The third digits we add are both 1 so the result will be 0 and we have to carry a 1 to the next significant digit. In this case its a 1 again so the result will be 0 and the 1 gets carried again. The next digit is a 0 so the one can be added with no overflow and the the result is a 1. The answer in binary is:

0000000 00000000 00000000 00010000 is 16.

It took me a while to figure all of this out, I had a real tough time with it in school. The best way to do it is to set up a whole bunch of practice problems and then check yourself on them. I found the calculator in Windows has a scientific view that lets you enter a decimal number and then see it in binary. And also binary to decimal.

If you need anything else let me know

glad to help

Dave

someone else may be able to give a better explaination too.

Also, if it helps, I dont think (from what I've heard) that you need to do too much binary addition/subtraction on the test. Most of it is converting from binary to decimal and decimal to binary.

[This message has been edited by Dave Vick (edited July 24, 2001).]

here is a basic example 1 + 1 = 2

When you add 1 to 1 the bit will change to 0 but then you have to carry the 1 to next highest bit. It is the same as adding 9 + 1. In base 10 numbers the highest digit is a 9, anytime you add to the 9 you start over at the beginning and increment the next most significant digit.

19

+ 1

the 9 becomes a zero and you carry the one to the left and add it to the digit there, in this case it becomes a two, so the answer is 20. If it would have been a nine also then it would have started over at zero and the 1 would have carried to the left again until it found a digit it could be added to that didn't exceed nine. Binary works the exact same way.

look at 12 + 4

starting at the right we add the two together, the first two digits are 0 + 0 so they are both 0. The third digits we add are both 1 so the result will be 0 and we have to carry a 1 to the next significant digit. In this case its a 1 again so the result will be 0 and the 1 gets carried again. The next digit is a 0 so the one can be added with no overflow and the the result is a 1. The answer in binary is:

0000000 00000000 00000000 00010000 is 16.

It took me a while to figure all of this out, I had a real tough time with it in school. The best way to do it is to set up a whole bunch of practice problems and then check yourself on them. I found the calculator in Windows has a scientific view that lets you enter a decimal number and then see it in binary. And also binary to decimal.

If you need anything else let me know

glad to help

Dave

someone else may be able to give a better explaination too.

Also, if it helps, I dont think (from what I've heard) that you need to do too much binary addition/subtraction on the test. Most of it is converting from binary to decimal and decimal to binary.

[This message has been edited by Dave Vick (edited July 24, 2001).]

Dave

Snylt Master

Ranch Hand

Posts: 55

posted 14 years ago

Yes thanks for your help Dave! I understand the +4 and so on but..... I meant the two compliment rule. Add 1. You can't add 4 when you work with 2 complements can you?

Hope you can stand me asking so many question. I'm very new to programming of this kind. Mostly vbscript , javascript before java. I've read the section of bits in Khalids book and in Simon Roberts Phillip Heller. Every time I've read something about I think for myself.. Ohhh now I've got it , but something always comes up and I'm back to where I started.

Ps. I think I have the >> << >>> shifting right. It's just when it comes to negativ numbers. Example -53 >> 2. When I compile an example the output writes -14. When I'm doing it in notepad... For myself I get -13?

eh?

// Snylt Master

[This message has been edited by Snylt Master (edited July 24, 2001).]

Hope you can stand me asking so many question. I'm very new to programming of this kind. Mostly vbscript , javascript before java. I've read the section of bits in Khalids book and in Simon Roberts Phillip Heller. Every time I've read something about I think for myself.. Ohhh now I've got it , but something always comes up and I'm back to where I started.

Ps. I think I have the >> << >>> shifting right. It's just when it comes to negativ numbers. Example -53 >> 2. When I compile an example the output writes -14. When I'm doing it in notepad... For myself I get -13?

eh?

// Snylt Master

[This message has been edited by Snylt Master (edited July 24, 2001).]

Preparing for the Java 2 Certification exam

Dave Vick

Ranch Hand

Posts: 3244

posted 14 years ago

I dont mind at all, helping other people helps me think and learn new things too.

Your right when you do the twos compliment you can't add 4, I just used that as an example, but the principle is the same, especially since you can only have 0's and 1's the actual value of 4 doesn't matter.

Lets look at your example: -53 >> 2

11111111 11111111 11111111 11001011 -53, becomes

11111111 11111111 11111111 11110010 after the shift

To find the decimal value use the twos compliment rule:

11111111 11111111 11111111 11110010

00000000 00000000 00000000 00001101 after flipping the bits.

When we add 1 to it we add the 1 to the right side bit (least significant) because it is also a 1 the result becomes a 0 and we carry a 1 to the next bit on the left. That bit is a 0 so adding 1 to it doesn't overflow and the result bit is a 1. The final answer would be:

00000000 00000000 00000000 00001110

this would be 14 in decimal so the result of your shift was -14.

When you get 13 you are probably not adding the 1. 13 is

00000000 00000000 00000000 00001101, which is the result after flipping all of the bits.

Another way of looking at carrying in binary:

Think of it this way, after you flip all the bits you have

00000000 00000000 00000000 00001101 this is 13, now you have to add 1. In decimal we know when you add one to a number the number increases. In binary it has to do the same thing. So if you have

00000000 00000000 00000000 00001101 and add 1, after you add the 1 but before you carry it over you have

00000000 00000000 00000000 00001100 this is 12, since we know the number has to increase you have to add a 1 back in somewhere. To do that you just keep moving left every 1 you see will become a 0, until you find a 0 and change it to a 1.

If that made it more confusing sorry, I tried to explain it another way, that helps for me alot.

Dave

[This message has been edited by Dave Vick (edited July 24, 2001).]

Your right when you do the twos compliment you can't add 4, I just used that as an example, but the principle is the same, especially since you can only have 0's and 1's the actual value of 4 doesn't matter.

Lets look at your example: -53 >> 2

11111111 11111111 11111111 11001011 -53, becomes

11111111 11111111 11111111 11110010 after the shift

To find the decimal value use the twos compliment rule:

11111111 11111111 11111111 11110010

00000000 00000000 00000000 00001101 after flipping the bits.

When we add 1 to it we add the 1 to the right side bit (least significant) because it is also a 1 the result becomes a 0 and we carry a 1 to the next bit on the left. That bit is a 0 so adding 1 to it doesn't overflow and the result bit is a 1. The final answer would be:

00000000 00000000 00000000 00001110

this would be 14 in decimal so the result of your shift was -14.

When you get 13 you are probably not adding the 1. 13 is

00000000 00000000 00000000 00001101, which is the result after flipping all of the bits.

Another way of looking at carrying in binary:

Think of it this way, after you flip all the bits you have

00000000 00000000 00000000 00001101 this is 13, now you have to add 1. In decimal we know when you add one to a number the number increases. In binary it has to do the same thing. So if you have

00000000 00000000 00000000 00001101 and add 1, after you add the 1 but before you carry it over you have

00000000 00000000 00000000 00001100 this is 12, since we know the number has to increase you have to add a 1 back in somewhere. To do that you just keep moving left every 1 you see will become a 0, until you find a 0 and change it to a 1.

If that made it more confusing sorry, I tried to explain it another way, that helps for me alot.

Dave

[This message has been edited by Dave Vick (edited July 24, 2001).]

Dave