CODEWITHSUNDEEP
clogicbit-manipulation
Andy
Andy

Reputation: 49

Using bitwise operators, find a logical not equivalent

Using only:

<< >> | ^ & +

How can I make a function that is equivalent to the logical not operator (!)?

Right now I have:

int i = (~x + 1) >> 31; 
int j = (x + 1) >> 31; 
i = i | j; 
i = i & 1; 
return i ^ 1;

It works for everything, but -1.

Upvotes: 4

Views: 5196

Answers (3)

David Grayson
David Grayson

Reputation: 87406

I will assume that you are working with ints that are 32-bit, signed, and use 2's complement notation. The unique thing about the number 0 is that neither 0 nor its negation have a 1 for the sign bits. This code would work if you were allowed to use the negation operator (-):

int not(int x)
{
    return (-x | x) >> 31 & 1 ^ 1;
}

You can't use minus, but that is ok because for all x we know that -x is equal to ~x + 1 which is equal to (x ^ -1) + 1. That's how 2's complement notation works. So the final answer is:

int not(int x)
{
    return ( (x^-1)+1 | x ) >> 31 & 1 ^ 1;
}

EDIT 1: Ok, here is the "ANSI" version of the function that makes no assumption about the size of the int and does not rely on the undefined behavior of right-shifting a signed int. It works for me in MinGW:

int not(int x)
{
    unsigned int y = x;
    return (( ((y^-1)+1) | y ) >> (sizeof(x)*8-1)) ^ 1;
}

Upvotes: 3

Mateen Ulhaq
Mateen Ulhaq

Reputation: 27201

Kind of 'cheating', but:

bool logicalNot(int i)
{
    return((bool)i ^ true);
}

I'm assuming there's nothing in the rules about composition of functions/typecasting/implicit type conversions?

Upvotes: 0

Omri Barel
Omri Barel

Reputation: 9480

Assuming that x is a 32-bit unsigned value:

x = x | (x >> 1)
x = x | (x >> 2)
x = x | (x >> 4)
x = x | (x >> 8)
x = x | (x >> 16)

At this point, if x was 0 then it's still 0. If it had a non-zero value, it now has the bit pattern 111....111.

With a two-complement representation, you can now simply add 1 and get the desired result:

x = x + 1

This solution assumes quite a bit about integer representation, types, etc.

(The "code" above is not valid C code, of course).

Upvotes: 0

Related Questions