Best way to generate the following bitmask for a given input?

Question

I'm trying to find out the best way to generate the following bitmask : - For a given input n, the output would be a bitmask which has the first (n-1) bits set, and all other bits unset.

Example:

if n = 1, output = 0x00000001 = 00000000000000000000000000000001 if n = 2, output = 0x00000003 = 00000000000000000000000000000011 if n = 3, output = 0x00000007 = 00000000000000000000000000000111

I know of the obvious iterative way(setting the bits one at a time), that would take O(n) time....I'm just wondering if there's any "bit-magic" that can do this in constant time, or at least sub-linear time (without using LUT !!)

Any takers ?

I didn't say n-1 bits set, I said the first n-1 bits(i.e 0 to n-1 th bit) would be set - Remember, the LSB is the 0th bit, so for n=1, first 0 bits (meaning only 0th bit) would be set !! — TCSGrad
– TCSGrad, Commented Mar 26, 2011 at 5:33
Oops, the above was in response to a comment, looks like he deleted it before I finished !! — TCSGrad
– TCSGrad, Commented Mar 26, 2011 at 5:34

Anomie · Accepted Answer · 2011-03-26 05:23:06Z

11

This should do it: (1 << n) - 1

answered Mar 26, 2011 at 5:23

Anomie

95.5k13 gold badges130 silver badges145 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Harvey Over a year ago

This doesn't work for n = 32. On my OSX 10.8.4 machine with clang 4.1: (1 << 32) => 1 which yields 0 instead of 0xFFFFFFFF.

Harvey Over a year ago

In fact, there's a comment in this answer by @DietrichEpp explaining it.

Harvey Over a year ago

After more research, there's a duplicate question that deals with n=32.

Collectives™ on Stack Overflow

Best way to generate the following bitmask for a given input?

1 Answer 1

3 Comments

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Linked

Related