在移位操作中使用 size_t 计数是否合适？

Question

这个看似微不足道的小问题，最近突然出现在我的脑海中，但在谷歌搜索了很多之后，我什至找不到关于这个问题的意见。仅引用循环和对象大小。

我知道人们喜欢例子，所以这里是第一个引起问题的例子：

uint64_t deltaSwap( const uint64_t b, const size_t delta, uint64_t mask )
{
    return b ^ mask ^ ( mask &=  b ^ b >> delta ) << delta;
}

一段时间以来我一直在尝试优化它，我非常清楚这不是编写正确代码的方法，尽管它给了我迄今为止最好的结果，至少对于 GCC，然后它发生在我身上。如果真要学究气，delta不应该是size_t类型的吗？

我从来没有真正理解什么时候使用 size_t，所以我从来没有真正理解过，但如果我知道，这不是正确的用法吗？

更新：这是对它的作用的简短解释，虽然不是它是如何做的，因为我不太确定如何解释它：

这是一个标准的 delta swap，这不是一个新的理想，代码工作正常，这不是真正的代码（但既然你问了），我真正做的就是试验它，以达到最佳性能，你在这里看到的版本，是我迄今为止最好的结果。

代码的目的是交换两位或更多位，如果你想交换第一位和最后一位，可以这样做：

deltaSwap(b, 63, 0x0000000000000001);

或者如果您希望反转位的顺序：

deltaSwap(b, 32, 0x00000000ffffffff);
deltaSwap(b, 16, 0x0000ffff0000ffff);
deltaSwap(b,  8, 0x00ff00ff00ff00ff);
deltaSwap(b,  4, 0x0f0f0f0f0f0f0f0f);
deltaSwap(b,  2, 0x3333333333333333);
deltaSwap(b,  1, 0x5555555555555555);

虽然对于这个特定任务，deltaswaps 可能不是最好的方法。

更新 2：补充一下，这是我能想到的最正确的在线答案（还没得到我的答案），而且编译器显然完美地优化了它。

uint64_t deltaSwap( const uint64_t b, const uint_fast8_t delta, const uint64_t mask )
{
    return b ^ ( mask & ( b ^ b >> delta ) ) ^ ( mask & ( b ^ b >> delta ) ) << delta;
}

我会缩短变量名以使其全部适应我的强迫症大脑（显然还有这个网站）强加的 80 个字符，但为了你们所有人，我愿意受苦。

Answer 1

来自 ISO/IEC 9899:1999 部分 6.5.7

If the value of the right operand is negative or is greater than or equal to the width of the promoted left operand, the behavior is undefined.

这意味着在您的情况下，delta 的要求是

0 <= delta < number of bits in the left operand

Answer 2

size_t 是一个整数类型，保证能够存储任何 sizeof() 操作的输出。这有几个含义：任何连贯内存块的字节数不能超过 size_t 可以表示为数字的字节数。这也意味着任何数组的元素都不能超过 size_t 可以表示的计数。此外，C 字符串的字符数不能超过 size_t 可以表示的长度。

至于何时使用 size_t，您应该始终将其用于存储内存大小、数组计数、数组索引和字符串长度，因为只有这样才能生成真正可移植的 C 代码。为此目的使用 int、long 或 uintX_t 可能在某些平台上有效，但在其他平台上可能会失败。请注意，即使 malloc 期望类型为 size_t 的参数，printf 也支持使用 %zu，并且 C 中的大多数字符串操作将其用作 input/output字符串长度。

至于混合不同宽度的整数：只有char、short、int、long和long long（以及它们的无符号对应项）是 C 中真正的本机整数。其他整数类型只是这些本机类型之一的别名，这些本机类型是后来的 C 标准添加的。当在一个操作中混合不同的类型时，较小的类型被提升为较大的类型，除非两种类型都小于 int，在这种情况下它们都被提升为 int，因为 C 执行所有操作在 int 或更大的类型上，从不在较小的类型上：

char a = 1;
char b = 2;
char c = a + b;
// Last line is in fact: char c = (char)( (int)a + (int)b );

long l = 20;
long m = m * b;
// Last line is in fact: long m = l * (long)b;

因此，如果您混合使用 uint64_t 和 size_t，那么要么两者都成为 uint64_t 作为本机类型的任何类型，要么它们都成为 size_t 的任何类型本机类型，以较大者为准，除非两者都小于 int，在这种情况下两者都变为 int.

因此使用 size_t 进行移位是完全可以的，因为任何整数类型都可以在移位操作的任一侧使用。

Answer 3

If you really want to be pedantic, shouldn't delta be of type size_t?

不，如果你真的想学究气，delta应该只是一个无符号整数类型，能够容纳至少范围内的值[=16] =] 到 sizeof(uint64_t) * CHAR_BIT。在你的情况下是 [0, 63]。没有必要让它成为 size_t.

I never really understood when to use size_t, so I never really do, but if I were to, wouldn't this be correct usage?

就代码的正确性而言，还可以。在优化方面，它没有多大意义。 size_t 用于保存大小，因为它是一种保证能够保存对象的最大可能大小的类型。它肯定 not 保证比普通 unsigned 或任何其他无符号整数类型快（请参阅答案底部）。

另一件需要注意的重要事情是：

 b ^ mask ^ ( mask &=  b ^ b >> delta ) << delta

是undefined behavior according to the C standard, since you are using the value of a variable while also applying a side effect to it in the same statement (see paragraph 6.5 point 2, page 76 here).

做你想做的正确方法是：

mask &= b ^ (b >> delta);
return b ^ (mask ^ (mask << delta));

在任何情况下，使用移位运算符时都要格外小心，因为它们优先于其他位运算符。使用额外的括号或将表达式拆分为多行不会影响性能并提高可读性。一个体面的编译器将毫无问题地优化上述内容。

现在，回到你问这个问题的真正原因：优化。

优化代码的正确方法是让编译器选择您需要的变量的最佳大小。为此，您只需要一个字节，并且可以使用 stdint.h 中的 uint_fast8_t，这是最快的（实现定义的）无符号整数类型，宽度至少为 8 位。编译器将为其目的选择最快的宽度。

综上所述，优化代码的正确方法是：

uint64_t deltaSwap( const uint64_t b, const uint_fast8_t delta, uint64_t mask )
{
    mask &= b ^ (b >> delta);
    return b ^ (mask ^ (mask << delta));
}

根据您的操作，如果 GCC 尚未为您内联代码，那么将函数声明为 inline __attribute__ ((always_inline)) 也可能是有意义的，尽管编译器通常更善于确定何时内联内联代码和何时不。您的函数很可能已经内联了。

还有一件更重要的事情：使用正确的优化标志通常比手动调整代码更重要。例如，对于上面的代码，您可能希望使用 -Ofast -march=native 进行编译，甚至可能需要其他标志，具体取决于您在何处使用该函数（例如，如果在循环中使用 -ftree-vectorize）。

除上述之外：假设公式已经简化为它的核心。

在移位操作中使用 size_t 计数是否合适？

Is it proper to use size_t for count in a bitshift operation?

c

bit-manipulation

size-t

bit-shift

bitwise-operators