Using bit masking to set 0 to 1 and everything else to 0

Question

How could I use bit masking to make all the bits in a number 1 if they were all 0, and all 0 if they were not?

Using an unsigned variable:

So, if I have 0000-0000, I would like that to become 1111-1111. If I have 0101-0110 (or 0000-0001, or 1111-1111, etc), I would like that to become 0000-0000.

Is this possible to do without using any conditional?

Answer 1

Sure, it's possible:

int y = 0xff;
y = ~(y & 1 | y>>1 & 1 | y>>2 & 1 | ...) - 1

But unless this is an academic exercise, you really shouldn't. If you're concerned about performance, y = y != 0 is almost certainly faster.

Explanation:

y & 1 takes the first bit of the number. y >> k shifts the number right by k bits, allowing us to get that bit by y >> k & 1. We simply | them together, which results in one if any bit is set or zero if not. Subtracting 1 gives us 0 if any bit was set, and -1 if not. The binary representation of -1 is 1111...

Shift:

1010 - y
1010 - y >> 0
 101 - y >> 1
  10 - y >> 2
   1 - y >> 3

Take the first bit:

   0 - y >> 0 & 1
   1 - y >> 1 & 1
   0 - y >> 3 & 1
   1 - y >> 4 & 1

Or them:

   1 - 0 | 1 | 0 | 1

Negate:

0000 - 1-1

Answer 2

Not in an efficient way probably.

If you really want you can maybe:

int mask = 0;
int result = 0;


for(int i = 0; i < sizeof(number) * 8; i++)
{
    mask |= number & 1 << i;
}


for(int i = 0; i < sizeof(number) * 8; i++)
{
    result |= mask & 1 << i;
}

~result is your answer.

Answer 3

How about this:

def check_for_zero(value):
    # Same as "if value == 0: return 0; else: return 1"
    # value must be an 8-bit number.

    # Need to check all 8 bits of value.  But we can compress it...
    x = value | (value >> 4)
    # Now just need to check the low 4 bits of x.  Compress again...
    x = x | (x >> 2)
    # Now just need to check the low 2 bits of x.  Compress again...
    x = x | (x >> 1)
    # Now just need to check the low 1 bit of x.  Success!
    return x & 1

def expand_to_8bit(bit):
    # Same as "if bit == 0: return 0; else: return 255"
    # Must pass bit == 0 or bit == 1

    # bit is a 1-bit value.  Expand it...
    x = bit | (bit << 1)
    # x is a 2-bit value.  Expand it...
    x = x | (x << 2)
    # x is a 4-bit value.  Expand it...
    x = x | (x << 4)
    # x is a 8-bit value.  Done!
    return x

def foo(value):
    x = check_for_zero(value)
    x = x ^ 1  # Flips the bit
    return expand_to_8bit(x)