• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Ron McLeod
  • Rob Spoor
  • Tim Cooke
  • Junilu Lacar
Sheriffs:
  • Henry Wong
  • Liutauras Vilda
  • Jeanne Boyarsky
Saloon Keepers:
  • Jesse Silverman
  • Tim Holloway
  • Stephan van Hulst
  • Tim Moores
  • Carey Brown
Bartenders:
  • Al Hobbs
  • Mikalai Zaikin
  • Piet Souris

A Practice Question for You (Bit Shifting)

 
Ranch Hand
Posts: 3271
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
While writing the most recent post on my blog, I stumbled upon this little gem of a question. See if you can get the correct answer.



See if you can get the right answer. I won't give the answer here, but you can get it for yourself by simply compiling and running this.

Edited by Corey McGlone: Fixed a Typo in the Subject Line
[ June 16, 2004: Message edited by: Corey McGlone ]
 
Ranch Hand
Posts: 159
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
hi Corey..

i try to calculate the question by hand but it gave me a different result with what it executed do(i got -7 )

byte require 8 bits therefore
13 in binary is 11110011
to change it to -13 i ~ 11110011 become 00001100
then i add 1 1
become ---> 11110011( equal to -13 in decimal)

-13 >>> 1 mean
11110011 >>> 1
result : 01111001 which it is not the same as -7


could you give us some explanation on it...
i try to read your last blog, but still don;t understand...

thanks
 
Ranch Hand
Posts: 298
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Even I have not been able to understand how its happening, but I feel that we are working on a byte so there must be some conversion trick which is required.

when we are working a byte, does any type of conversion from byte to int happens or not???

Please someone try to find out in this question.

Kaps
 
Ranch Hand
Posts: 187
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
13=00001101
promote to int(32 bits)[byte short are promoted to ints, int stays as int, long stays as long.]
~13=1111....10010

-13=1111....10011
-13>>>1=0111...1001

cast to byte(8 bits)
11111001
~=00000110
+1=111
-7

When I say "=" what i mean is "same as"
[ June 17, 2004: Message edited by: Swamy Nathan ]
 
Ranch Hand
Posts: 7729
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Corey, you now have a class named after you! I'm going to pass this one around the office.
 
Beny Na
Ranch Hand
Posts: 159
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hi Swamy, thanks for your explanation..
but i still have a question. i marked your answer with ** where i still confused.

13=00001101
promote to int(32 bits)[byte short are promoted to ints, int stays as int, long stays as long.]
~13=1111....10010

-13=1111....10011
-13>>>1=0111...1001

cast to byte(8 bits)
11111001

**(question-1)
~=00000110

**(question-2)
+1=111
-7

Why we have to flip the bits as in question-1 and add it to 1(question-2)??


thanks...
scjp
 
Corey McGlone
Ranch Hand
Posts: 3271
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Originally posted by Barry Gaunt:
Corey, you now have a class named after you! I'm going to pass this one around the office.



I have a what?!?

Okay, I've given you a day to do this: So now I suppose I'll explain the answer, in case you haven't figured it out already.

We start with "byte b = -13;" Well, what does 13 look like in binary? To determine 2's complement, start with the binary of +13, flip the bits, and add 1.

00001101 (Positive 13)
11110010 (Flipped Bits)
11110011 (Add 1 - This is -13 in binary)

Now, we execute this line of code: b >>>= 1;

Here's where the trap is laid. What does a compound assignment operator do? Most people would simply rewrite that line like this:

b = b >>> 1;

That, however, isn't quite correct. The compound assignment operators include an implicit cast to the type of the left hand operand. Therefore, to rewrite b >>>= 1, you should really write this:

b = (byte)(b >>> 1);

If you'd like to read more about compound assignment operators, you can do so here.

So, what does that mean to us? Well, first of all, when we're working with bit shifts, we promote each operand. The left and right hand operands are promoted to ints (if they aren't already ints or longs). Note that the two values are promoted separately. Unlike a multiplcation operator, in which the two operands must be of the same type, one operand can be an int while another is a long and this operator will still work. Regardless, in our case, we promote b to an int and the value 1, which is a literal and is therefore already and int, is just fine.

So what does b look like as an int? Well, it looks like this:

11111111 11111111 11111111 11110011

We just add 24 1's to the byte to end up with -13 represented as an int. Now that we've performed the conversion, we can perform the operation. Let's shift b to the right 1 position using an unsigned right shift (that means we're going to push a 0 into the left side). Our value now looks like this:

01111111 11111111 11111111 11111001

Okay, no problem, right? Now, however, we need to take into account the fact that the compound assignment operator that we used includes a cast to turn that value into a byte. Anything that doesn't fit in the least-significant 8 bits is chopped off! The trap has been sprung! We're left with this:

11111001

That, of course, is a negative value. To determine what it represents, we flip the bits and add 1.

11111001 (Original Value)
00000110 (Flipped Bits)
00000111 (Added 1 - This is 7 so the original value was -7)

And we end up with b being set to the value -7, just as the program shows if you execute it.

I stumbled over this one at first, myself, before I had to take a look at what I was doing and smacked myself in the head. :roll: I guess it's a good thing I usually compile all of the code I post.

This is a good little question for any of you mock exam writers out there. I hope you all understand what is happening now.

Corey
[ June 17, 2004: Message edited by: Corey McGlone ]
 
Beny Na
Ranch Hand
Posts: 159
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Thanks for such a great explanation Corey..

i understand it now for others question except when i shift it with 32.
for exapmle : -24>>>32 result in -24, why?

-24 in binary : 11111111 11111111 11111111 11101000
shitf 32 bits to
the right : 00000000 00000000 00000000 00000000
flips it : 11111111 11111111 11111111 11111111
add 1 1
become 00000000 00000000 00000000 00000000

what happen then??

sorry if i am asking to much question Corey...because i want the concept can be applied to any cases.

thanks a lot for your time...


scjp
 
Corey McGlone
Ranch Hand
Posts: 3271
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Remember that the shift range of an int is 0 to 31 - you can't shift something 32 positions. You can determine the shift distance by evaluating the 5 or 6 least significant bits of the right-hand operand (5 bits for an int 6 for a long). In your case, you need to do this:



As you can see, trying to shift by 32 is the same as shifting by 0. That's why you end up with the same value that you started with.
 
Swamy Nathan
Ranch Hand
Posts: 187
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator



The same thing can also be done by this.
If your right argument or shift distance is "shift" and your left argument or variable to be shifted is "x" then first u check the promoted type of x.
Is promoted type of x a int or a long.
(byte, short, int have promoted types int. long is long)
If the type is an int do this
shift=shift%32
else if the type is a long do this
shift=shift%64

If the resulting shift is negative (<0) then do this
shift=shift+32.

Useful trick to get at the actual shift distance.
[ June 17, 2004: Message edited by: Swamy Nathan ]
 
Corey McGlone
Ranch Hand
Posts: 3271
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Originally posted by Swamy Nathan:
shift=shift%32



This works, of course, because performing a "% 32" returns the 5 least significant bits of the value, which is exactly the same as the operation I showed above using bit operations. Ahhh yes, the wonderful world of powers of 2.
 
Greenhorn
Posts: 14
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I had a funny incident. when i saw this question posted, i began solving it, but later it turned out that the way i solved it was wrong. but to my astonishment i got the right answer ( -7 ).

this is what i did :


b = b >> 1 ( this is wrong , but bear with me till i finish )

-13 in binary , take + 13 first

0000 1101

flip bits

1111 0010

add 1

1111 0011

alright now right shift by one.

we have

1111 1001

now this is negative , to get the decimal number , do the usual stuff.

flip bits

0000 0110

add 1

0000 0111

we get it !!!

-7

but its wrong , wrong ,wrong.....


Thanks to Corey , he explained the right way...

thanks dude !!!

keep up the good work.
 
Beny Na
Ranch Hand
Posts: 159
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Thanks a lot for all of you...
it help me a lot to understand the concept and to solve the problem.
 
Forget Steve. Look at this tiny ad:
Thread Boost feature
https://coderanch.com/t/674455/Thread-Boost-feature
reply
    Bookmark Topic Watch Topic
  • New Topic