C语言中读写整数最高位的最便携方法是什么？

Question

在C语言中，读写整数的最高位最便携的方法是什么？

这是Bloomberg的面试问题。当时我没有给出最好的答案。请问有人能回答吗？

- Josh Morrison

---

GNU C 不是很便携... - osvein

Answer 1

如果类型是无符号的，那么很容易：

(type)-1-(type)-1/2

对于有符号值，我不知道任何方法。如果你找到了一种方法，它将回答 SO 上几个未解决的问题：

C 问题：off_t（和其他有符号整数类型）的最小和最大值

是否有任何方法在编译时计算整数类型的宽度？

也许还有其他问题。

- R.. GitHub STOP HELPING ICE

---

你是什么意思（类型）-1？能给我真正的C代码吗？有点困惑，可能我没理解。抱歉。 - Josh Morrison

我尝试了，但没有得到正确的结果。我错在哪里了？你能给我一个简短的程序片段吗？你如何证明这是正确的？我还是很困惑... - Josh Morrison

你得到了什么结果？你期望得到什么结果？在一个32位int系统上，(unsigned)-1-(unsigned)-1/2给出了预期的0x80000000。 - R.. GitHub STOP HELPING ICE

另一种可能性是 ~((unsigned)-1 >> 1)。 - Christoph

有趣的是，使用空格，例如(type)-1 - (type)-1 / 2，答案更易读... :-/. - Tony Delroy

Answer 2

首先需要注意的是，如果我们谈论的是有符号整数，那么没有一种可移植的方式可以访问最高位；标准中没有定义单一可移植表示，因此“最高位”的含义原则上可能会有所不同。此外，C语言不允许直接访问位表示；您可以将int作为char缓冲区进行访问，但是您不知道“最高位”位于哪里。

如果我们只关心有符号整数的非负范围，并且假设该范围的大小是2的幂（如果不是，则我们需要再次关注有符号表示）：

#define INT_MAX_BIT (INT_MAX - (INT_MAX >> 1))
#define SET_MAX_BIT(x) (x | INT_MAX_BIT)
#define CLEAR_MAX_BIT(x) (x & ~INT_MAX_BIT)

类似的方法也可以用于无符号整数，它可以用来获取真正的最高位。

- bdonlan

---

这仅适用于在 limits.h 中指定了限制的整数类型。例如，对于 off_t，它无效。 - R.. GitHub STOP HELPING ICE

@R，没错，但很难找到一种既高效又可移植的方法，既不使用“_MAX”宏，也不会引发未定义（或实现定义）的行为... - bdonlan

对不起，您能为我解释一下为什么 "#define INT_MAX_BIT (INT_MAX - (INT_MAX >> 1))" 起作用吗？ 我没听懂。 - Josh Morrison

通常 INT_MAX 的值具有所有 1 设置（假定对于某些 n，INT_MAX 等于 2^n-1）。右移一位会导致最高位被清除。然后从原始值中减去仅留下最高位设置。 - bdonlan

标准实际上对整数类型的表示方式有相当严格的限制 - 例如，有符号和无符号类型的最大值都必须是 2 ** N - 1。请参见第6.2.6.2节。 - caf

啊，我明白了；它实际上被限制在三种有符号整数表示中的一种。虽然没有什么规定符号位必须是“最高”位 :) - bdonlan

Answer 3

这是一个关于IT技术的有趣例子，使用了以下内容：

Built-in Function: int __builtin_clz (unsigned int x)

Returns the number of leading 0-bits in x, starting at the most
significant bit position. If x is 0, the result is undefined. 

第一次尝试：

int get_msb(int x) { return x ? __buildin_clz(x) == 0 : 0; }

注意：C语言中指定int或unsigned int参数的函数可以在不警告的情况下使用另一种类型进行调用，这是C语言的一个怪癖。但是，这可能涉及到转换——C++标准4.7.2表示：

如果目标类型为无符号类型，则结果值是与源整数同余的最小无符号整数（模2n，其中n是用于表示无符号类型的位数）。[注意：在二进制补码表示中，这种转换是概念性的，如果没有截断，位模式不会改变。]

这意味着如果它不是二进制补码表示，则位模式可能会被更改，这也将使这个“解决方案”无法可靠地工作。 :-(

克里斯的下面评论提供了一个解决方案（这里作为函数而不是预处理器宏）：

int get_msb(int x) { return x ? __buildin_clz(*(unsigned*)&x) == 0 : 0; }

- Tony Delroy

---

解决方法是 #define msb(x) __builtin_clz(*(unsigned)&x)，但这样你就不能在字面数字上使用它。GCC 的解决方法是 #define msb(x) ({ typeof(x) _x = x; __builtin_clz(*(unsigned)&_x); })。 - Chris Lutz

@Chris：很好...在上面的函数中，int x参数将会接收字面量，然后你可以按照你所建议的进行转换。我会更新上面的代码。谢谢！ - Tony Delroy

转换技术上属于未定义行为，这意味着它不能保证工作。在实践中，它将重新解释有符号值的地址为无符号值（这是正确的未定义行为，因为标准没有指定特定的符号表示方式），就像 union { int i; unsigned u; } u; u.i = x; return __builtin_clz(u.j); 一样。我使用了一个宏，这样它就可以适用于有符号和无符号的 int 类型，并仅为有符号版本调用 UB。但是，无论如何，你做什么都会变得必然依赖于平台。 - Chris Lutz

@Chris：是的，我知道，但如果GCC本身在任何古怪的系统上无法工作，我也不会感到惊讶... :-). - Tony Delroy

Answer 4

这个有什么问题吗？

int get_msb(int n){
    return ((unsigned)n) >> (sizeof(unsigned) * CHAR_BIT - 1);
    // or, optionally
    return n < 0;
};

int set_msb(int n, int msb){
    if (msb)
         return ((unsigned)n) |  (1ULL << (sizeof(unsigned) * CHAR_BIT - 1));
    else return ((unsigned)n) & ~(1ULL << (sizeof(unsigned) * CHAR_BIT - 1));
};

它处理字节序、字节中的位数，并且也适用于1的补码。

- ruslik

---

这假设采用二进制补码表示法。OP请求一种可移植的方式 :) - bdonlan

C标准并不限制“二进制补码或一的补码”这些选项。根据6.5.7.5，负数右移的结果完全是实现定义的；超出正值范围进行左移的结果是未定义的，原则上甚至可能会导致崩溃。 - bdonlan

也不可移植，因为 sizeof(X)*CHAR_BIT 假设没有填充位。 - R.. GitHub STOP HELPING ICE

使用模算术代替位运算技巧。 - R.. GitHub STOP HELPING ICE

Answer 5

#define HIGH_BIT(inttype) (((inttype)1) << (CHAR_BIT * sizeof(inttype) - 1))

使用示例：

ptrdiff_t i = 4711;
i |=  HIGH_BIT(ptrdiff_t);  /* set high bit */
i &= ~HIGH_BIT(ptrdiff_t);  /* clear high bit */

- rapm

---

请添加一些解释。 - Nilambar Sharma