Pick your types carefully.

Or correctness is the highest priority.

Competitive programmers use a number of bit tricks to squeeze every bit of performance. But as optimizing compilers continuously get smarter, we are often encouraged to stop performing bit shenanigans and trust our compilers.

Without doubt, the most well known and used in practice trick is integer division by 2 using bit shifting, so

becomes

which seems reasonable as each digit in binary representation corresponds to a power of 2. That’s also the reason why this approach can be easily extended to handle division by any power of 2 using right bit shifting.

But let’s peek under the hood and check out the assembly generated for

Turns out that for an signed integer version the generated code does not match our expectation

Turns out that compilers care about correctness and as such think about the negative integer case. If we were to use right bitwise shift on a negative number like -3 (0b11111111111111111111111111111101) we’d get 0b11111111111111111111111111111110 (-2) instead of an expected -1 (0b11111111111111111111111111111111), so compiler adds a sign, leftmost, bit to the original value, so we actually get the correct result: (-3 + 1) >> 1 == -1.

Obviously, this is not needed for unsigned integers, so the generated assembly looks exactly the way we expect

trimming down the number of instructions from 5 to 3. Let’s measure runtime impact of this difference using C++ benchmark

and singed integer version is 1.6X slower

The moral of the story? Picking the right type is not only important for designing APIs that are harder to misuse and easier to reason about, but can also affect performance. It’s not uncommon to see right bitwise shift on signed integers for division by 2, but unless we are absolutely sure it cannot be negative, in which case it would be better to use an unsigned integer type, such usage is incorrect.