Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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

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 ?

like image 589
TCSGrad Avatar asked Dec 28 '22 23:12

TCSGrad


1 Answers

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

like image 145
Anomie Avatar answered Feb 01 '23 12:02

Anomie