Logical Right Shift

[theotherindian]

Hey people,

I'm working on an assignment that requires me to right-shift a 32-bit integer with 0s rather than the most significant bit(which is what C does by default). I'm allowed to use binary operators &, ^, ~, | and logical operators +, ! and =. No if statements, no macros, nothing. Also, any integer that is declared should be less than or equal to 0xFF.

Any help will be appreciated!
Thanks!

[AndrewHunter]

Take a look at Prelude's Bit Manipulation Tutorial and then post the code you have and we can help.

[iMalc]

The easy way is to cast to unsigned, do the shift and then cast back again.
An unsigned shift to the right zero-fills the evacuated bits.
If you can't do that then just figure out how to make the mask value to 'and' the result with to cancel out the leading ones that get introduced by the shift.

[theotherindian]

@iMalc - I figured out the algorithm in pseudo-code. Here is how it goes:

if the int is shifted by n bits, declare an int with n 1s as the least significant bits (ex: if n = 3, the declared int would be 00000..00111).
then shift the declared int by (32-n) which will make shift the 1s to the most significant bits positions (now 1110000..0000).
then just perform a bitwise "&" on the original int and the declared int.

But the problem I'm having is how to declare an int with n 1s in the least significant bit positions (keeping in mind of course that I can't declare an int greater than 0xFF)...

If I can get a hint on how to do that, I think I can take it from there..

Thanks!

[theotherindian]

@iMalc - I figured out the algorithm in pseudo-code. Here is how it goes:

if the int is shifted by n bits, declare an int with n 1s as the least significant bits (ex: if n = 3, the declared int would be 00000..00111).
then shift the declared int by (32-n) which will make shift the 1s to the most significant bits positions (now 1110000..0000).
then just perform a bitwise "&" on the original int and the declared int.

But the problem I'm having is how to declare an int with n 1s in the least significant bit positions (keeping in mind of course that I can't declare an int greater than 0xFF)...

If I can get a hint on how to do that, I think I can take it from there..

Thanks!

[itCbitC]

You haven't stated how many times do you need to right shift the 32 bit integer by?
If int <= 0xff, then right shifting will push 0's not 1's from the left end as the MSB==0.

[KCfromNC]

What do you get when you shift 1 left by a certain number of bits? Look for a way to change from this value to one which sets the 1 to a 0 and all the 0s below it to 1s, which is what your mask has to be. If you need help, write out binary numbers from decimal 1 to 16 and notice what's just before or after the values which are all 1s in the LSBs.

[KCfromNC]

You haven't stated how many times do you need to right shift the 32 bit integer by?
If int <= 0xff, then right shifting will push 0's not 1's from the left end as the MSB==0.

As I read it, he's limited to using 0xFF or less in code he writes, but the input can be any signed 32-bit value?

[itCbitC]

As I read it, he's limited to using 0xFF or less in code he writes, but the input can be any signed 32-bit value?

Yep! and thanks for clearing the mists swirling in my head because any other way wouldn't make sense.

[iMalc]

Think about what you get if you take a number with lots of consecutive bits set and then add 1. Does such a number look easier to produce? You can then subtract 1 and you get a nice mask.

[Salem]

> requires me to right-shift a 32-bit integer with 0s rather than the most significant bit, which is what C does by default
You got this wrong.
right-shift of an unsigned value always inserts zeros.
right-shift of a signed value MAY shift in zeros, or MAY shift in the sign bit.