Set last `n` bits in unsigned int

Question

How to set (in most elegant way) exactly n least significant bits of uint32_t? That is to write a function void setbits(uint32_t *x, int n);. Function should handle each n from 0 to 32.

Especially value n==32 should be handled.

Solution 1

If you meant the least-significant n bits:

((uint32_t)1 << n) - 1

On most architectures, this won't work if n is 32, so you may have to make a special case for that:

n == 32 ? 0xffffffff : (1 << n) - 1

On a 64-bit architecture, a (probably) faster solution is to cast up then down:

(uint32_t)(((uint64_t)1 << n) - 1)

In fact, this might even be faster on a 32-bit architecture since it avoids branching.

Solution 2

Here's a method that doesn't require any arithmetic:

~(~0u << n)

Solution 3

The other answers don't handle the special case of n == 32 (shifting by greater than or equal to the type's width is UB), so here's a better answer:

(uint32_t)(((uint64_t)1 << n) - 1)

Alternatively:

(n == 32) ? 0xFFFFFFFF : (((uint32_t)1 << n) - 1)

Solution 4

const uint32_t masks[33] = {0x0, 0x1, 0x3, 0x7 ...

void setbits(uint32_t *x, int n)
{
   *x |= masks[n];
}

Solution 5

If n is zero then no bits should be set based on the question.

const uint32_t masks[32] = {0x1, 0x3, 0x7, ..., 0xFFFFFFFF};

void setbits(uint32_t *x, int n)
{
    if ( (n > 0) && (n <= 32) )
    {
        *x |= masks[--n];
    }
}

View more solutions

Comments

[Jim Rhodes]

by last do you mean high order or low order?

[phuclv]

this question handles any values in the range [0, 64]: Creating a mask with N least significant bits set

[TonyK]

The other answers handle it perfectly well. (1 << 32) - 1 is 0xFFFFFFFF.

[Oliver Charlesworth]

@Tony: No they don't. Shifting beyond the length of the type is undefined.

[Oliver Charlesworth]

Unnecessary amounts of coding, but at least it will give the right answer.

[Oliver Charlesworth]

@Tony: You're downvoting because I gave an answer containing portable code with well-defined behaviour?

[Cartesius00]

@Marcelo: I guess it works even without u64 test, just the first version, doesn't it?

[Alex S]

@TonyK: No, it doesn't work, because shifting a 32-bit integer by 32-bits isn't supported on most architectures (certainly not on Intel).

[James McNellis]

Right: "The behavior is undefined if the right operand is...equal to the length in bits of the promoted left operand." [C++11 §5.8/1]

[nos]

@TonyK n == 32 shifts one past the width, which is undefined behavior.

[Cartesius00]

@TJD: I guess unnecessary amount of memory access.

[Alex S]

@TonyK: This has as much to do with the CPU as the compiler, and it doesn't work my i686-apple-darwin11-llvm-gcc-4.2.

[Cartesius00]

@Marcelo: Anyway, Marcelo, answer accepted. Good to know about 1<<32 issue.

[Jens Gustedt]

I don't think that this answer is correct. 1 is of type int and 1 << n could go wrong for much more cases than you assume. A first shot would be to use 1U << n but then the OP explicitly wanted uint32_t. For that the correct thing would be to use UINT32_C(1) << n.

[Alex S]

@MichaelKrelin-hacker: Nice. Though I assume you meant (uint32_t)((-1)>>(32-n))

[Michael Krelin - hacker]

oops. But no, I meant (uint32_t), with signed it will stay with all bits set for all values of n.

[Michael Krelin - hacker]

I see you edited your guess, still no, I want to cast before shifting.

[Alex S]

@JensGustedt: Other than 32, which has already been discussed, which other value(s) doesn't my answer handle correctly?

[Alex S]

@MichaelKrelin-hacker: Ah, sorry; I misunderstood what you were trying to do. Yes, that works, but it also has an edge-case: n == 0.

[Jens Gustedt]

@MarceloCantos, IRC left shift with 31 on an 32 bit integer leads to overflow => undefined behavior. And then int is only guaranteed to be 16 bit wide by the standard. In summary your version can fail for values from 16 to 31.

[Jens Gustedt]

@MarceloCantos, also in your faster version, what is the purpose of cast n to uint64_t? You should "cast" the 1 this is what determines the type of the expression.

[Jens Gustedt]

@OliCharlesworth, casting a constant? This should just be UINT64_C(1). And then your alternative solution doesn't work on architectures with 16 bit int, but doesn't work for 32 bit int either, because for 31 you have an overflow.

[David Rodríguez - dribeas]

Branching would most probably not be an issue here... there are specific assembly instructions to handle the simpler cond?a:b cases like this. Try to compile into assembly and check the output.

[Alex S]

@JensGustedt: Ah yes; good points; I've fixed it. When you said, "much more cases", I thought you meant something more calamitous.

[Jens Gustedt]

@MarceloCantos, at least the 31 is calamitous. Please fix it by just putting a 1U instead of 1 as a base of the shift.

[Jens Gustedt]

@OliCharlesworth, why casting a constant where the language gives you the right tool to just specify the right one?

[DarkDust]

+1, no memory access, no branches and no special cases. I consider this to be the most elegant solution.

[Eric]

@DarkDust: Except this (sometimes) fails for n = 32, since shifting a uint_32t by 32 is undefined behaviour.

[xuhdev]

You can just use ~0UUL or ~0UL instead of 0xsomanyf. It'll be more platform independent as you don't need to know the exact size of int or long or whatever.

[Alex S]

@xuhdev: The OP stipulated uint32_t.

[wonder.mice]

If you can't shift all the way through, then shift half of that and then do the rest: (1 << n/2 << n - n/2) - 1 (sort of a joke)

[underscore_d]

Your case for n >= 32 does not help, since the prior unchecked shift will still be done, and if n >= sizeof(TheType) * CHAR_BIT, that's UB, which isn't affected by whether you try to paper over it after the fact.

[paxdiablo]

Perhaps "goals" should also include "readable/understandable code" :-)

[Harvey]

@paxdiablo Yeah, that's why I stated the goals: to indicate that readable code was NOT the goal. :)

[Harvey]

@underscore_d What's "UB" mean? It's ok if the first line is produces a bad value for n>=32 because the next line corrects it. I've added a program to the answer that proves the algorithm. Honestly, it has been so long that I needed the program to prove it to myself.

[underscore_d]

@Harvey Undefined behaviour poisons the entirety of a program as soon as you invoke it. You cannot "correct it" by overwriting it afterwards. And it means absolutely nothing if you find that the code happens to produce the correct results when tested, because the UB means that it's not required to and can break at any time (when ported to a different architecture, compiler, Standard revision, etc.). Code that invokes UB is bad and shouldn't be posted as a recommendation, and that's the end of it.

[Harvey]

@underscore_d I get your point, and I respectfully disagree. Example: x = uint32_t(1) << 40; x = 7; Even if the first statement is undefined behavior (for some values, e.g. 40), the second line is very much defined behavior and the result is ok. Unless "undefined behavior" includes crashing an app or memory corruption, it's good.

[Harvey]

@underscore_d To be fair, I was surprised that << doesn't mean shift for my current compiler. It clearly means shift with rotation which I wouldn't have expected (undefined behavior).

[underscore_d]

@Harvey There's nothing to disagree about. The letter of the Standard is that once UB occurs, the behaviour of the entire program is undefined. It doesn't matter if you then do something that completely replaces the object; UB has occurred, and it can't be undone. Sure, practically, probably nothing will go wrong, as compilers don't make it their mission to ruin your life. But it's formally ill-formed code, so it's irresponsible to portray it as being fine.

[Harvey]

@underscore_d I agree with you in principle. In this case, I'm ok with this specific code because I think "undefined behavior" probably means "undefined, but sane". In other words, no compiler writer is going to guarantee that the value returned is what you expected, but they will probably guarantee not to modify anything other than that value producing no side effects. I'll add a comment with your warning.

[phuclv]

there are many ways to handle that case without a branch: Creating a mask with N least significant bits set

[phuclv]

The -1 ^ part is the same as a NOT operation, so just use ~((1 << (32 - n)) - 1)