set most significant bit in C

Question

I am trying to set the most significant bit in a long long unsigned, x. To do that I am using this line of code:

x |= 1<<((sizeof(x)*8)-1);

I thought this should work, because sizeof gives size in bytes, so I multiplied by 8 and subtract one to set the final bit. Whenever I do that, the compiler has this warning: "warning: left shift count >= width of type"

I don't understand why this error is occurring.

Solution 1

The 1 that you are shifting is a constant of type int, which means that you are shifting an int value by sizeof(unsigned long long) * 8) - 1 bits. This shift can easily be more than the width of int, which is apparently what happened in your case.

If you want to obtain some bit-mask mask of unsigned long long type, you should start with an initial bit-mask of unsigned long long type, not of int type.

1ull << (sizeof(x) * CHAR_BIT) - 1

An arguably better way to build the same mask would be

~(-1ull >> 1)

or

~(~0ull >> 1)

Solution 2

use 1ULL << instead of 1 <<

Using just "1" makes you shift an integer. 1ULL will be an unsigned long long which is what you need. An integer will probably be 32 bits and long long probably 64 bits wide. So shifting:

1 << ((sizeof(long long)*8)-1)

will be (most probably):

1 << 63

Since 1 is an integer which is (most probably) 32 bits you get a warning because you are trying to shift past the MSB of a 32 bit value.

Solution 3

The literal 1 you are shifting is not automatically an unsigned long long (but an int) and thus does not have as many bits as you need. Suffix it with ULL (i.e., 1ULL), or cast it to unsigned long long before shifting to make it the correct type.

Also, to be a bit safer for strange platforms, replace 8 with CHAR_BIT. Note that this is still not necessarily the best way to set the most significant bit, see, e.g., this question for alternatives.

You should also consider using a type such as uint64_t if you're assuming unsigned long long to be a certain width, or uint_fast64_t/uint_least64_t if you need at least a certain width, or uintmax_t if you need the largest available type.

Comments

[this]

And then you are still making assumptions. It is better to calculate the msb and set it, if you want to be portable.

[Arkku]

@this Yes, sizeof(type) * CHAR_BIT is not the best solution, but at least it removes the hard-coded 8 from the OP's approach.

[Artur]

I like these new ways although they are not obvious.

[mazhar islam]

Up voted for a nice answer, still can you put some light on how ~(-1ull >> 1) or ~(~0ull >> 1) be a better way?

[Filipe Gonçalves]

@rakeb.void Because it's more compact, doesn't depend on CHAR_BIT or other constants, and is easier to read (and smaller).

[AnT stands with Russia]

@rakeb.void: It is "better" becuase it has less redundancy in it. The original variant depends on the target type in two ways: the literal suffix ull and the shift distance sizeof(x) * CHAR_BIT. This alternative method has only one dependency - the literal suffix. Although it is less obvious at the first sight, it should be known to the programmer as an idiom.

[too honest for this site]

C does not guarantee 2s complement actually, so any implementation relying on that would be implementation dependent at best.

[too honest for this site]

An integer is not "most probably" 32 bits. There are many architectures with 16 bit integers, some with 24 bit integers, etc. (you are right about UB, however).

[rici]

To avoid depending on a literal suffix, use an expression of the correct integer type: ~((x|~x)>>1) or ~(~(x^x)>>1), both of which should be constant-folded by any self-respecting compiler. (This only works if x is at least as wide as an int, but I don't think that's a problem in this case.)

[AnT stands with Russia]

@rici: Yes, but that requires introduction of an extra variable, which will involve type name in the declaration (which is equivalent to literal suffix in this regard). In OP's case you are not allowed to destroy x's value in that fashion. The original value of x has to be preserved with the exception of the most significant bit.

[rici]

@ant: the value of x is not destroyed by that code. The statement x |= ~((x|~x)>>1) is well-defined provided that x has a value (which it must in order to use the |= operator).

[rici]

Another solution to "set the MSB": x = ~(~x << 1 >> 1). Requires x to be unsigned and at least as wide as an int.

[Artur]

@Olaf: Yes I am aware of that - int's size does not even solely depend on architecture but compiler also. One can have 2 compilers for same cpu and with different int sizes. There are many many nuances here.