Set n highest bits

Question

I have the following function that sets the N high bits, for example. set_n_high (8) == 0xff00000000000000

uint64_t set_n_high(int n) { uint64_t v = 0; int i; for (i = 63 ; i > 63 - n; i--) { v |= (1llu << i); } return v; } 

Now just out of curiosity, is there a way in C to accomplish the same thing without using a loop (or lookup table)?

EDIT: n = 0 and n = 64 are cases that need to be handled, as the loop option does.

Answer 1

If you are ok with the idle case n = 0 , you can simplify it to

 uint64_t set_n_high(int n) { return ~UINT64_C(0) << (64 - n); } 

If, in addition to this, you have everything with a “strange number of shifts” (undefined behavior, but Works On My Machine), you can simplify this even further

 uint64_t set_n_high(int n) { return ~UINT64_C(0) << -n; } 

If you are ok with the idle case n = 64 , you can simplify it to

 uint64_t set_n_high(int n) { return ~(~UINT64_C(0) >> n); } 

If this means you must check n , it will not be faster. Otherwise it could be.

If you're out of order, if none of them work, it gets harder. Here is a suggestion (maybe the best way)

 uint64_t set_n_high(int n) { return ~(~UINT64_C(0) >> (n & 63)) | -(uint64_t)(n >> 6); } 

Note that the negation of an unsigned number is well defined.

Answer 2

 uint64_t set_n_high(int n) { return ((1llu << n) - 1) << (64-n); } 

Answer 3

taking the @harold answer well and changing it a bit:

  uint64_t set_n_high(int n) { int carry = n>>6; return ~((~0uLL >> (n-carry)) >> carry); } 

Answer 4

Use a conditional expression to handle n == 0 , and then it becomes trivial.

 uint64_t set_n_high(int n) { /* optional error checking: if (n < 0 || n > 64) do something */ if (n == 0) return 0; return -(uint64_t)1 << 64 - n; } 

In fact, there is no good reason to do something more complicated. Listing from int to uint64_t fully specified, as is negation and shift (because the sum of the shift is guaranteed in [0.63] if n is in [0.64]).

Answer 5

Well, I present a strange look.
:)

 /* works for 0<=n<=64 */ uint64_t set_n_high(int n) { return ~0llu << ((64 - n) / 4) << ((64 - n) * 3 / 4); } 

Answer 6

For what it's worth, from the messages so far (which process n from 0-64), this one creates the smallest build on x86_64 and raspberry pi (and performs 1 branch operation) (with gcc 4.8. 2). It looks pretty readable.

 uint64_t set_n_high2(int n) { uint64_t v = 0; if (n != 0) { v = ~UINT64_C(0) << (64 - n); } return v; }