CODEWITHSUNDEEP
c++cbit-manipulation
Alessandro Power
Alessandro Power

Reputation: 2472

Bit hack to return one of two values depending on the value of the second

Suppose x is a bit mask (ie all of its bits except for one are 0) and y is either a bit mask or is equal to 0. I need a bit hack to return x if y is non-zero and return zero if y is zero.

Here's one possible solution: take the base-2 logarithm of x and y (using de Bruijn sequence) and subtract them, storing the value in d. Then y << d will return x unless y was zero to begin with.

Two problems with this approach: 1) if y is zero, technically the base-2 logarithm is undefined. Not sure if that matters though, because even if d is some garbage value, y << d should still return zero if y is zero; 2) if d is negative, the right-shift operator does not become a left-shift operator (according to Google search), meaning that I'll have to include some sign checking.

I'm convinced that there's a simpler approach, but I can't find it and would appreciate some help.

EDIT: to clarify, I'm looking for the fastest way to do this. The obvious if (y == 0) return 0; else return x uses an if statement and hence suffers from the adverse effects of branch prediction, which is why I'm resorting to convoluted base-2 log solutions.

Upvotes: 1

Views: 354

Answers (3)

njuffa
njuffa

Reputation: 26185

The use of the ternary operator would be preferred on most common processor architectures:

/* if y != 0, return x, else return 0 */
int select1 (int x, int y)
{
    return y ? x : 0;
}

The use of the ternary operator does not typically involve the use of branches on modern processor architectures, since it can easily be implemented in branchless fashion by using conditional moves (e.g. on x86), instruction predication (e.g. on ARM), or select instructions (e.g. on some GPUs).

If use of the ternary operator is not desired or allowed, and a bit-twiddly solution is required, one could (assuming the platform uses two's complement representation for integers) use:

/* if y != 0, return x, else return 0 */
int select2 (int x, int y)
{
    return (0 - (y != 0)) & x;
}

Note that select2() is likely to be slower than select1(). Example: If I compile the above functions for the x86-64 architecture my compiler produces this instruction sequence for select1()

test      edx, edx
cmovne    edx, ecx
mov       eax, edx
ret

but this longer instruction sequence for select2():

mov       r8d, 1
test      edx, edx
cmovne    edx, r8d
neg       edx
and       edx, ecx
mov       eax, edx
ret

Note that neither instruction sequence involves branching as part of value selection, but the instruction sequence in select2() requires more instructions to be executed and also has a longer dependency chain, compared to the instruction sequence in select1().

Upvotes: 5

dwks
dwks

Reputation: 602

Just take y and use its bits to form a string of all 1's if it was nonzero, then AND this with x. The silly way of doing this is linearly but you can do it with a binary method too (not given).

#include <stdio.h>
#include <limits.h>

int foo(int x, int y) {
    int z = 0;
    for(int z = 1; z < CHAR_BIT * sizeof(int); z ++) {
        y |= y << z;
    }
    return x & y;
}

int main() {
    printf("%lx\n", foo(0x1000, 0xdead));
    return 0;
}

That should run in constant time. You can unroll the loop of course.

Upvotes: 0

DarkPhantom
DarkPhantom

Reputation: 155

static_cast<bool>(y) * x

Upvotes: 5

Related Questions