6

I'm currently working on a project, in which I need bit sets. I'm using an array of uint64_t's for the bitset.

My current problem is, that whenever I want to set or check a bit I need to do an operation like this:

uint64_t index = 42;
bArr[index/64] |= (((uint64_t)1)<<(index%64));

I can rewrite the division and modulo with some clever and and bitshift operations as well, but I'm concerned about the cast of 1. I need this cast, since otherwise the 1 is seen as a 32-bit unit. As seen in this example - you get wrong output without a cast:

uint64_t bArr[4];                           // 256 bits 
bArr[0] = bArr[1] = bArr[2] = bArr[3] = 0;  // Set to 0

uint64_t i = 255;
bArr[i/64] = (bArr[i/64] | (((uint64_t)1)<<(i%64))); 

uint32_t i2;
for (i2 = 0; i2 < 256; i2++) {
  if ((bArr[i2/64] & (((uint64_t)1)<<(i2%64))) != 0) {
    printf("bArray[%" PRIu32 "] = 1\n", i2);
  }
}

Can I get around this cast in a clever way? I was thinking that the performance is probably suffering from a cast at every read/write...

Matthias
  • 175
  • 6
  • Do *not* rewrite the division and modulo to be "clever"; the compiler is certainly clever enough to already do those optimizations for you. Also consider using `CHAR_BIT * sizeof bArr[0]` instead of `64`, to avoid magic numbers. – unwind Jun 28 '16 at 19:53
  • @unwind Thanks for the tip. I'll test it with my code. This is probably the case though. – Matthias Jun 28 '16 at 19:53
  • If you're looking for speed, provide a `const uint64_t` table with the 64 different ULL constants (1 pre-shifted into all possible places) and index into that. – tofro Jun 28 '16 at 22:24

4 Answers4

4

The result type of << operator is the type of the left operand (after integer promotions) that's why you need to use the correct type: 1 is of type int but you need type uint64_t.

You can use either:

(uint64_t) 1

or 

UINT64_C(1)  /* you have to include <stdint.h> */

or

1ULL

(for the last one assuming unsigned long long is 64-bit in your system which is very likely).

But they are all equivalent: all these expressions are integer constant expressions and their value is computed at compile time and not at run time.

ouah
  • 142,963
  • 15
  • 272
  • 331
  • Great to know, that this happens at compile time and won't affect performance (only uglifies the code)... – Matthias Jun 28 '16 at 19:53
  • 1
    Detail `unsigned long long` is at least 64-bit, so `bArr[index/64] |= 1ULL <<(index%64);` will certainly work. Assuming `unsigned long long` is 64-bit is not needed. – chux - Reinstate Monica Jun 28 '16 at 19:56
  • @chux Will it break when `unsigned long long` is greater than 64-bit? I'm not exactly sure what is happening. Could you try to explain, what happens without a cast? I saw the wrong output and was assuming it had to do something with the width (and therefore successfully tried the cast). I would like to know, why the code broke ... – Matthias Jun 28 '16 at 20:04
  • @chux you are right, it was actually to make the point in my last sentence that three expressions are equivalent (but for this I should also mention `uint_least64_t` can be different than `unsigned long long`). – ouah Jun 28 '16 at 20:05
  • 1
    @Matthias it will work the same if `unsigned long long` width is greater than 64-bit. – ouah Jun 28 '16 at 20:09
  • The only down-side to using `1ULL` vs. `UINT64_C(1)` I see, in a more complex expression, is that `1ULL` may go to a wider type than `uint64_t` and create issues like [here](http://stackoverflow.com/a/19453213/2410359). Certainly rare in 2016 as `unsigned long long` is commonly 64-bit. – chux - Reinstate Monica Jun 28 '16 at 20:13
  • 1
    @chux nice example. When dealing with `uint64_t` objects for example, I would prefer `(uint64_t) 1` so I'm sure the computations will be done using the exact same type. – ouah Jun 28 '16 at 20:18
  • Agreed. For robust code I prefer `((uint64_t)1)` over `1ULL` to insure the desired type too. Yet with simple `bArr[index/64] |= 1ull <<(index%64);`, Using `ULL` is appealing. `INT64_C(1)` is best for portability as `uint64_t` need not exist, yet `int_leastN_t` will. But that `uint64_t` is assumed to exist in OP's example. – chux - Reinstate Monica Jun 28 '16 at 20:30
3

A cast in and of itself does not affect performance. It's a compile time construct that tells the compiler the type of an expression.

In this case, they're all integer casts and expressions, so there should be no performance impact.

dbush
  • 205,898
  • 23
  • 218
  • 273
  • Oh, you again :) So as you'll probably remember this is pretty much your code (only with `uint64_t`). Also do you know what size is probably the best to use for the array `uint64_t`, `uint32_t`, `uint16_t` or even `uint8_t`? I'm having L1/L2 cache size in my mind, but don't know much about it... – Matthias Jun 28 '16 at 19:51
  • *a cast [...] is a compile time construct that tells the compiler the type of an expression* it's not correct to say a cast is a compile time construct when in most cases it's not. – ouah Jun 28 '16 at 20:01
3

C offer macros for this which will expand the integer constant to the type int_leastN_t.

INTN_C(value)
UINTN_C(value)

Example

#include <stdint.h>.
bArr[index/64] |= UINT64_C(1) << (index%64);

In general it is better to avoid casting. Sometimes casting unexpectedly make the expression narrower than hoped.

Benefit of UINT64_C: uint_least_64_t/int_least_64_t types must exist (C99). int64_t/uint64_t are optional.

chux - Reinstate Monica
  • 143,097
  • 13
  • 135
  • 256
  • Nice macro, thanks for the tip :) In this case casting should be fine, since I always working on `uin64_t` right? – Matthias Jun 28 '16 at 19:55
  • Is there any benefit in choosing `INT64_C` over a cast to `(int64_t)`? – a3f Jun 28 '16 at 20:29
  • 1
    @a3f Answer edited to address a benefit. When N is >= `unsigned/int` width and `(u)intN_t` exist, certainly `INTN_C()` and casting `(intN_t)` behave alike. – chux - Reinstate Monica Jun 28 '16 at 20:34
1

If I understand you correctly, you want a literal 1 that is at least 64 bits long. You can get this without any casts by writing 1ull instead of just 1. This creates an unsigned long long literal with the value 1. However, the type is not guaranteed not to be longer than 64-bits, so if you rely on it being exactly 64-bits you may need a cast after all.

amaurea
  • 4,950
  • 26
  • 35