Check if at least a bit is set without jumping

▲
2
▼

I'm trying to find an efficient way to check if an integer is zero without jumping.

I have two integer variables in and out. If in is zero, I want out to be zero. If in is not zero, I want out to be one.

If it may help, I know that in will be zero or a power of two (only one set bit). I also know that the most significant and the less significant bits are never set.

I could do the obvious : out = (in == 0 ? 0 : 1); But that implies a jump which is costly.

I could do something like this out = (in * 0xFFFFFFFF) >> 63;. This implies a multiplication and shift that I would like to avoid, but I can't find a way. Maybe it's not possible.

Any other way I could do this without jump and only using bit-wise operators and arithmetic?

Thanks

c++
bit-manipulation
asked on Stack Overflow Jul 10, 2018 by Mathieu Pagé

3 Answers

▲
6
▼

This will differ with architecture but the code doesn't compile to a jump on Intel CPUs.

This code:

int square(int in) {
    int out = (in != 0);
    return out;
}

is compiled to:

square(int):
    xor     eax, eax
    test    edi, edi
    setne   al
    ret

or:

square, COMDAT PROC
    xor      eax, eax
    test     ecx, ecx
    setne    al
    ret      0
square ENDP

by msvc, clang and gcc with O2:

It is only a jump with no optimization which you would never do anyway.

answered on Stack Overflow Jul 10, 2018 by Jerry Jeremiah • edited Jul 10, 2018 by Jerry Jeremiah
▲
2
▼

I've also found the need to do this, to index a length-2 array at 0 for zero values and 1 for non-zero values.

Cast the int to bool, and then back to int. This does not jump on almost every compiler I've tried (gcc, clang, recent MSVC) except MSVC pre-2018. I recommend you check the assembly code to make sure on your platform.

int one_if_nonzero_else_zero(int value) { return (bool) value; }

EDIT: This does not satisfy your constraint "only using bit-wise operators and arithmetic" but this cast takes advantage of assembly optimization and will be very efficient.

EDIT: Your "obvious" solution out = (in == 0 ? 0 : 1); results in identical assembly code as solutions posted by Jerry Jeremiah and myself on gcc, clang, and msvc. No jump after optimization! I suggest you use it for clarity.

answered on Stack Overflow Jul 10, 2018 by Taylor Nichols • edited Jul 10, 2018 by Taylor Nichols
▲
0
▼

I have two integer variables in and out. If in is zero, I want out to be zero. If in is not zero, I want out to be one.

Try this:

int in = ...;
int out = !!in;

Live Demo

C++ has an implicit conversion defined from int to bool, so in as a bool will be false when in is 0, and will be true otherwise.

Then !false will be true, and !true will be false.

Then !true will be false, and !false will be true.

Then there is also an implicit conversion defined from bool to int, so true as an int will be 1, and false will be 0.

Thus, out will be 0 when in is 0, and will be 1 otherwise.

answered on Stack Overflow Jul 10, 2018 by Remy Lebeau • edited Jul 10, 2018 by Remy Lebeau

User contributions licensed under CC BY-SA 3.0