0

Why does ~((~0ULL) >> size << size) for size between 1 inclusive and 64 inclusive evaluate to 0 when size = 64?

chew socks
  • 1,406
  • 2
  • 17
  • 37
  • 9
    Shifting a 64-bit type by 64 is undefined behaviour. – chris Oct 09 '13 at 04:25
  • Oh, didn't know that. I did find that in the standard now that I knew to look. Is there an alternative/better way to get the first `size` bits set on? – chew socks Oct 09 '13 at 04:26
  • 1
    `~(unsigned long long(-1) >> 1 >> (size - 1) << 1 << (size - 1))` would work if you knew size was always > 0 – rici Oct 09 '13 at 04:30
  • Check whether you're dealing with less than 64 bits first. For less than 64 bits, do what you're doing. For 64 bits or more, the result is always (~0ULL). The trick is doing this without introducing a branch. –  Oct 09 '13 at 04:30
  • @rici - why cast `-1` to an unsigned type when the intent is `~0` anyway? –  Oct 09 '13 at 04:32
  • By the way, although the implementation could do pretty well anything for the computation of -1 >> 64, the actual behaviour mimics the underlying hardware which only uses the low-order 6 bits of the shift count. – rici Oct 09 '13 at 04:32
  • @Steve314: because right-shifting a negative number is implementation-specified, whereas right-shifting an unsigned number has clear semantics. Although I could well have used ~0ULL. – rici Oct 09 '13 at 04:33
  • @rici - I meant doing unsigned arithmetic. By `~0` I was just describing the intent as the bitwise complement of zero. –  Oct 09 '13 at 04:34
  • @Steve314: Are you suggesting you know a way to do it without branching, or that it would be nice if I could find one? – chew socks Oct 09 '13 at 04:54
  • @chew - I was suggesting that I couldn't be bothered figuring it out just to put in a comment. In any case, the details are probably compiler/platform specific (e.g. can you guarantee that `x < 64` will give `0` or `1` *without* using a branch to decide which?). I didn't see your solution (which is branchless because it doesn't need a test - why didn't I think of that?!?) until I had already posted. –  Oct 09 '13 at 07:55

2 Answers2

2

Shifting by a value greater than or equal to the size of the value is undefined behaviour.

This is probably in the standard to keep the shift operation fast enough and just mapping underlying hardware operations.

For reasons that are not entirely clear to me for example even in x86 assembly shifting is done modulo the size of the register. I'm no hardware engineer but probably that was the most efficient thing to do.

Another unfortunate limitation is that shifting by a negative count is not the same as shifting by a positive count in the opposite direction and is instead just UB. This sometimes requires adding extra conditionals in computations.

6502
  • 112,025
  • 15
  • 165
  • 265
1

Because what you are doing is undefined behavior. Don't shift a 64 bit integer by 64 places.

Edited to add: Why does left shift operation invoke Undefined Behaviour when the left side operand has negative value?

Community
  • 1
  • 1
It'sPete
  • 5,083
  • 8
  • 39
  • 72