4

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 ?

TCSGrad
  • 11,898
  • 14
  • 49
  • 70
  • 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 Mar 26 '11 at 05:33
  • Oops, the above was in response to a comment, looks like he deleted it before I finished !! – TCSGrad Mar 26 '11 at 05:34
  • Possible duplicate of [Set last \`n\` bits in unsigned int](http://stackoverflow.com/questions/8128674/set-last-n-bits-in-unsigned-int) – Silicomancer Dec 20 '16 at 19:17

1 Answers1

10

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

Anomie
  • 92,546
  • 13
  • 126
  • 145
  • 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 Jun 25 '13 at 00:12
  • In fact, there's a comment in [this answer](http://stackoverflow.com/a/2404474/47078) by @DietrichEpp explaining it. – Harvey Jun 25 '13 at 00:20
  • After more research, there's a [duplicate question](http://stackoverflow.com/questions/8128674/set-last-n-bits-in-unsigned-int) that deals with n=32. – Harvey Jun 25 '13 at 00:32