C - BitArray - Set single bit of uint64_t

Question

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...

Personable

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. – Welty

@Welty Thanks for the tip. I'll test it with my code. This is probably the case though. – Personable

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. – Marrissa

Answer 1

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.

Cyanotype

Great to know, that this happens at compile time and won't affect performance (only uglifies the code)... – Personable

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. – Aeronaut

@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 ... – Personable

@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). – Cyanotype

@Personable it will work the same if unsigned long long width is greater than 64-bit. – Cyanotype

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. Certainly rare in 2016 as unsigned long long is commonly 64-bit. – Aeronaut

@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. – Cyanotype

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. – Aeronaut

Answer 2

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.

Smarmy

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... – Personable

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. – Cyanotype

Answer 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.

Aeronaut

Nice macro, thanks for the tip :) In this case casting should be fine, since I always working on uin64_t right? – Personable

Is there any benefit in choosing INT64_C over a cast to (int64_t)? – Armitage

@Armitage 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. – Aeronaut

Answer 4

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.

Legitimacy