CODEWITHSUNDEEP
cbit-manipulationmicro-optimization
ntldr
ntldr

Reputation: 143

Implementing "logical not" using less than 5 bitwise operators

As part of my CS classes I've recently completed the pretty popular "Data Lab" assignments. In these assignments you are supposed to implement simple binary operations in C with as few operations as possible.

For those who are not familiar with the "Data Lab" a quick overview about the rules:

The task is to implement a logical not called 'bang' (where bang(x) returns !x) by only using the following operators: ~ & ^ | + << >>

The function prototype is defined as 

int bang(int x)

The best implementation I could find (using 5 operators) was the following:

return ((x | (~x +1)) >> 31) + 1

However there seems to be a way to accomplish this with even less operators, since I found a result website[1] from some German university where two people apparently found a solution with less than 5 operator. But I can't seem to figure out how they accomplished that.

[1] http://rtsys.informatik.uni-kiel.de/~rt-teach/ss09/v-sysinf2/dlcontest.html (logicalNeg column)

To clarify: This is not about how to solve the issue, but how to solve it with less operations.

Upvotes: 12

Views: 4266

Answers (3)

Paul Hankin
Paul Hankin

Reputation: 58271

If you take the liberty of assuming that int addition overflow is well-defined and wraps (rather than being undefined behavior), then there's a solution with four operators:

((a | (a + 0x7fffffff)) >> 31) + 1

I think you are assuming that overflow is defined to wrap otherwise your function ((x | (~x + 1)) >> 31) + 1 has undefined behavior for x=INT_MIN.

Upvotes: 3

Chris Dodd
Chris Dodd

Reputation: 126243

Only slightly cheating:

int bang(int x) {
    return ((x ^ 0xffffffffU) + 1UL) >> 32;
}

is the only way I can think of to do it in only 3 operations. Assumes a 32-bit int and 64-bit long...

Upvotes: 5

Keith Nicholas
Keith Nicholas

Reputation: 44298

why not just :-

int bang(int x)
{
    return 1 >> x;
}

Upvotes: 2

Related Questions