CODEWITHSUNDEEP
ccastingbit-shiftmemory-efficientbitarray
Matthias
Matthias

Reputation: 175

C - BitArray - Set single bit of uint64_t

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

Upvotes: 6

Views: 1738

Answers (4)

chux
chux

Reputation: 153457

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.

Upvotes: 3

ouah
ouah

Reputation: 145829

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.

Upvotes: 4

dbush
dbush

Reputation: 223852

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.

Upvotes: 3

amaurea
amaurea

Reputation: 5067

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.

Upvotes: 1

Related Questions