Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Efficiently make an int that has a 1 all 1s but one that is 0 stay 0

I have an assignment that asks to do a number of functions only using these operators:

! ~ & ^ | + << >>

In some of the problems it is useful to make some integer, x, become all 1s if it contains any 1s but stay 0 if it is 0. The reason I do this is so I can return y or z like this:

// One of the two conditional values is now 0
int conditionalA = mask&y;
int conditionalB = ~mask&z;

// One of the values is combined with 0 using |
int out = conditionalA|conditionalB;

return out;

where I made mask like this:

// Make any x other than 0 all 1s
int mask = x;
mask |= mask>>1;
mask |= mask>>2;
mask |= mask>>4;
mask |= mask>>8;
mask |= mask>>16;

mask |= mask<<1;
mask |= mask<<2;
mask |= mask<<4;
mask |= mask<<8;
mask |= mask<<16;

There must be a better way to make mask all 1s or 0s but I can't think of a more efficient solution. Again, it is important that 0 remains 0 if x was 0.

Edit: If statements are not an option

like image 813
asimes Avatar asked Feb 01 '13 22:02

asimes


2 Answers

Assuming 2's complement:

int mask = !x + ~0;

The ! maps any nonzero value to 0 and 0 to 1, then we add ~0 (-1) to get -1 and 0 respectively.

like image 119
ecatmur Avatar answered Nov 07 '22 09:11

ecatmur


How about:

x = (x | -x) >> 31; // Note this is implementation specific.

Ok, I'm using - which isn't allowed, so it's not the right answer here. I'll leave it here as a novelty.

like image 3
JasonD Avatar answered Nov 07 '22 10:11

JasonD