C - BitArray - 设置uint64_t的单个位

Question

我目前正在从事一个需要使用位集的项目，我正在使用一个uint64_t 数组来表示位集。

我当前的问题是，每当我想要设置或检查一位时，我需要进行像这样的操作：

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

我也可以通过一些聪明的与和位移操作重新编写除法和模运算，但我关心1的转换。我需要这个转换，否则1将被视为32位单元。如此例所示 - 如果没有转换，您将得到错误的输出：

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);
  }
}

我能以巧妙的方式避免这个强制类型转换吗？我认为性能可能因为在每次读写时都进行了强制类型转换而受到影响...

- Matthias

---

不要聪明地重写除法和取模运算;编译器已经足够聪明，为您执行这些优化。此外，请考虑使用 CHAR_BIT * sizeof bArr [0] 而不是 64，以避免使用魔数。 - unwind

@unwind 感谢您的提示。我将用我的代码进行测试。这很可能是情况。 - Matthias

如果您想要提高速度，请提供一个 const uint64_t 表，其中包含 64 个不同的 ULL 常量（1 预先移位到所有可能的位置），并从中进行索引。 - tofro

Answer 1

<<运算符的结果类型是左操作数的类型（在整数提升后），因此您需要使用正确的类型：1是int类型，但您需要uint64_t类型。

您可以使用以下任一选项：

(uint64_t) 1

或者

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

或者

1ULL  

(假设你的系统中 unsigned long long 是 64 位，那么最后一个例子是成立的，这非常可能。)

但它们都是等效的：所有这些表达式都是整数常量表达式，它们的值在编译时计算而不是运行时计算。

- ouah

---

详细说明unsigned long long至少为64位，因此bArr[index/64] |= 1ULL <<(index%64);一定可以工作。不需要假设unsigned long long是64位。 - chux - Reinstate Monica

@chux 当 unsigned long long 大于 64 位时，它会崩溃吗？我不确定发生了什么。你能否尝试解释一下，在没有强制转换的情况下会发生什么？我看到了错误的输出，并且认为它与宽度有关（因此成功尝试了强制转换）。我想知道为什么代码会崩溃... - Matthias

@chux 你是对的，实际上我的最后一句话是要表明三个表达式是等价的（但为此我还应该提到 uint_least64_t 可能与 unsigned long long 不同）。 - ouah

@Matthias 如果 unsigned long long 的宽度大于64位，它将以相同的方式工作。 - ouah

@chux 不错的例子。例如，当处理 uint64_t 对象时，我更喜欢使用 (uint64_t) 1，这样我就可以确保计算是使用完全相同的类型完成的。 - ouah

Answer 2

一个cast本身并不会影响性能。它是编译时的构造，用来告诉编译器表达式的类型。

在这种情况下，它们都是整数cast和表达式，因此不应该有性能影响。

- dbush

---

哦，你又来啦 :) 所以，你可能还记得这基本上是你的代码（只不过换成了uint64_t）。另外，你知道对于数组使用哪种大小最好吗？uint64_t、uint32_t、uint16_t甚至是uint8_t？我有 L1/L2 缓存大小在脑海中，但是对此不是很了解... - Matthias

“一个强制类型转换（cast）是编译时的构造，用于告诉编译器表达式的类型。”这并不正确，因为在大多数情况下，强制类型转换并不是编译时的构造。 - ouah

Answer 3

C语言提供了宏来将整数常量扩展为int_leastN_t类型。

INTN_C(value)
UINTN_C(value)

示例

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

一般情况下最好避免强制类型转换。有时候强制类型转换会让表达式比期望的更窄。

---

UINT64_C 的好处：必须存在 uint_least_64_t/int_least_64_t 类型（C99）。int64_t/uint64_t 是可选的。

- chux - Reinstate Monica

---

不错的宏，谢谢你的提示 :) 在这种情况下，强制转换应该没问题，因为我总是在处理 uin64_t 对吧？ - Matthias

选择使用INT64_C是否比强制转换为(int64_t)更有优势？ - a3f

@a3f 答案已编辑以解释一个好处。当 N >= unsigned/int 宽度且 (u)intN_t 存在时，确实 INTN_C() 和强制转换 (intN_t) 的行为类似。 - chux - Reinstate Monica

Answer 4

如果我理解您的意思正确，您想要一个至少为 64 位长的字面值 1。您可以通过编写 1ull 而不是仅仅的 1 来 获得此内容，这样就可以不需要任何强制转换了。这将创建一个值为 1 的 unsigned long long 字面值。但是，该类型不能保证不超过 64 位，因此如果您依赖于它恰好为 64 位，则可能仍然需要强制转换。

- amaurea