Rounded power of 2 divider done with bitwise operations fails for some inputs

Question

I wrote the following function:

int divideBy2Power(int x, int y) { return (x >> y) + (x < 0 && x << (32 - y)); }

which is supposed to compute {x / (2^y)} (rounding towards zero) in an extremely efficient manner (i.e. without branching!)

In testing it works for most inputs, but for divideBy2Power(-2, 0) it produces -1. Likewise, x=-1, y=0 produces 0 (not -1). It works for bunches of other negative numbers.

I'm on a 32-bit machine and I checked that x << 32 produces zero.

Any ideas?

Just a comment: you do have a branch in there with the `&&` operator. — Zan Lynx, Apr 02 '12 at 22:42
@Robᵩ: To be pedantic, `-2 >> 0` is merely implementation-defined. — Oliver Charlesworth, Apr 02 '12 at 22:49
The correct way to avoid branching is to use &, not &&, but you need to use & and shift to get the sign bit. It gets messy, but it can be done without branching. — DRVic, Apr 02 '12 at 23:01
I'm currently trying `(!(!(x << y)) & ((x >> 31) & 1)) + (x >> y)` but that doesn't work for -2147483646[0x80000002],1 for example. It gives -1073741822[0xc0000002] but should be -1073741823[0xc0000001] — vaebnkehn, Apr 02 '12 at 23:27
Testing that `x << 32 == 0` does **not** necessarily tell you that `x << n == 0` given `n == 32`. The former is likely to be constant-folded to 0 at compile time. In particular if you have an x86 CPU then shifting a 32 bit register by 32 is a nop. — caf, Apr 03 '12 at 01:23

Oliver Charlesworth · Answer 1 · 2012-04-02T23:19:07.900

4

You have two sources of undefined behaviour (UB), and one of implementation-defined behaviour (IDB):

x << 32 is UB for all x (assuming you have 32-bit int on your platform).
-2 << y is UB for all y.
-2 >> y is IDB for all y.

So any behaviour you observe for divideBy2Power(-2, 0) is entirely down to "chance" (for lack of a better term).

I realise that this doesn't directly answer your question, but in a sense, it doesn't matter. Invoking UB twice in one expression should be avoided at all cost; you need to find a different way to write your function.

edited Apr 02 '12 at 23:19

answered Apr 02 '12 at 22:51

Oliver Charlesworth

267,707
33
569
680

I was seeing unexpected behavior in trying to reproduce the OPs results locally, now I know why :) – fbrereto Apr 02 '12 at 22:57

score 1 · Answer 2 · answered Apr 02 '12 at 22:53

1

Ah, the answer is obvious once you break down the expression:

New code:

#include <stdio.h>

int divideBy2Power(int x, int y)
{
    int a = x >> y;
    int b = x < 0;
    int c = x << (32-y);
    printf("a=%d\n", a); 
    printf("b=%d\n", b); 
    printf("c=%d\n", c); 
    printf("b&&c=%d\n", (b&&c));
    return a + (b && c); 
}

int main()
{
    printf("%d\n", divideBy2Power(-2, 0));
    return 0;
}

Then you clearly see that b=1, c=-2 so b&&c = 1.

answered Apr 02 '12 at 22:53

Zan Lynx

53,022
10
79
131

@OliCharlesworth: Assuming the Intel x86 or x86_64 instruction set, the result will always come out the same. But yes, on a different CPU it might not. – Zan Lynx Apr 02 '12 at 23:09
Not necessarily. "UB" isn't just a way to express that different platforms have different hardware instructions; it's also means that the compiler is free to make assumptions when optimising. These assumptions may in turn lead to surprising results for pathological inputs! Here's an article about a similar (but different) case: http://www.airs.com/blog/archives/120. – Oliver Charlesworth Apr 02 '12 at 23:15

score 0 · Answer 3 · edited May 23 '17 at 10:34

Your first problem is that you're adding the result of a binary AND comparison && (not bitwise); which will be either 0 or 1. That's nonsensical, it DOES use a branch, and has other questionable logic.

Secondly, see https://stackoverflow.com/a/9874464/1110687 for an explanation of why this fails with signed numbers and what exactly is undefined behavior in this case. It's about left-shifting but it applies to right-shifting also.

score -1 · Answer 4 · answered Apr 02 '12 at 22:54

-1

Perhaps you meant

int divideBy2Power(int x, int y) { return (x >> y) + ( (x < 0)& (x << (32 - y))); }

Note the extra parentheses. The order of precedence on << and >> is often not what you expect.

answered Apr 02 '12 at 22:54

DRVic

2,481
1
15
22

Doesn't make a difference here. – Oliver Charlesworth Apr 02 '12 at 22:55
Does on my system. If it doesn't on yours, that would have to do with ( x << ( 32-y) ) being undefined. – DRVic Apr 02 '12 at 22:58
`<<`, `>>` and `<` all have higher precedence than `&` or `&&`. – Oliver Charlesworth Apr 02 '12 at 23:00
It doesn't make a difference anywhere, unless you're using a compiler that doesn't properly implement C precedence. – Jim Balter May 15 '12 at 04:48

Rounded power of 2 divider done with bitwise operations fails for some inputs

4 Answers4