Win a copy of Learn Spring Security (video course) this week in the Spring forum!

# bit shifting

Christophe Lee
Ranch Hand
Posts: 142
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
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.

Dave Vick
Ranch Hand
Posts: 3244
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).]

Snylt Master
Ranch Hand
Posts: 55
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.

Christophe Lee
Ranch Hand
Posts: 142
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.

Dave Vick
Ranch Hand
Posts: 3244
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

hope that helps
Dave

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

Snylt Master
Ranch Hand
Posts: 55
OK Dave!
So adding one at the rightmost bit isn't the same as adding "1"
if the positive bitpattern is
0000 0110 then the negativ would be
1111 1001
1111 1000
is this right??

Dave Vick
Ranch Hand
Posts: 3244
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).]

Snylt Master
Ranch Hand
Posts: 55
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?

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

Dave Vick
Ranch Hand
Posts: 3244
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

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).]

Snylt Master
Ranch Hand
Posts: 55
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).]

Dave Vick
Ranch Hand
Posts: 3244
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).]

Snylt Master
Ranch Hand
Posts: 55
Thanks Dave! I've got it now . I did a lot of tests and It's seems to be right!
Thanks again!
------------------
Preparing for the Java 2 Certification exam