使用位运算符将无符号整数转换为无符号短整型

Question

我希望将无符号整型（32位）A 转换为无符号短整型（16位）B，转换方式如下：

• 如果 A <= 2^16-1，则 B=A
• 如果 A > 2^16-1，则 B=2^16-1

换句话说，如果 A 大于 16 位允许的最大值，则将其设置为最大值。如何使用位操作或其他非分支方法实现此目标？

- Ross

---

你是不是想说"...然后B=2^16-1"？ - Vlad

如果A > 2^16-1，你是不是想说B=2^16-1？ - wkl

Answer 1

这将适用于无符号值：

b = -!!(a >> 16) | a;

或者，类似的东西：

static inline unsigned short int fn(unsigned int a){
    return (-(a >> 16) >> 16) | a;
};

- ruslik

---

我也喜欢你的解决方案。谢谢。 - Ross

Answer 2

不用分支查找两个整数的最小值：

http://graphics.stanford.edu/~seander/bithacks.html#IntegerMinOrMax

在一些罕见的机器上，分支非常昂贵并且没有条件移动指令的情况下，以上表达式可能比明显的方法“r = (x < y) ? x : y”更快，即使它涉及两个额外的指令。（通常，最明显的方法是最好的。）

为了开始，这里有一个简单的基准测试。我试图随机获取50/50的大和小值：

#include <iostream>
#include <stdint.h>

int main() {
    uint32_t total = 0;
    uint32_t n = 27465;
    for (int i = 0; i < 1000*1000*500; ++i) {
        n *= 30029; // worst PRNG in the world
        uint32_t a = n & 0x1ffff;
        #ifdef EMPTY
            uint16_t b = a; // gives the wrong total, of course.
        #endif
        #ifdef NORMAL
            uint16_t b = (a > 0xffff) ? 0xffff : a;
        #endif
        #ifdef RUSLIK
            uint16_t b = (-(a >> 16) >> 16) | a;
        #endif
        #ifdef BITHACK
            uint16_t b = a ^ ((0xffff ^ a) & -(0xffff < a));
        #endif
        total += b;
    }
    std::cout << total << "\n";
}

在我的编译器（gcc 4.3.4在cygwin上使用-O3），NORMAL最快，其次是RUSLIK，然后是BITHACK，分别比空循环慢0.3、0.5和0.9秒。实际上这个基准测试并没有什么意义，我甚至没有检查生成的代码是否聪明到足以在某些地方胜过我。但我还是喜欢ruslik的方法。

- Steve Jessop

---

这段代码中有一个 < 符号，许多编译器（但不包括现代的gcc）会将其编译为一个分支语句。 - R.. GitHub STOP HELPING ICE

好的，显而易见的解决方案 r = (x < y) ? x : y 在大多数情况下更好。 - Ross

@Ross：嗯，从Anderson的许多调整技巧的注释中可以看出，他并不是没有错误。但这确实表明，在大多数常见的实现中，并没有一种明显的方式被“预期”更快，否则就会有人提交它 :-) - Steve Jessop

@Vlad：是的，但是为了避免分支而加入大量额外指令也不好。很难一概而论哪种更糟糕。 - Steve Jessop

@ruslik：确实，对于“如何在不使用分支的情况下完成此操作”的问题，在许多编译器和架构上，b = (a > 0xffff) ? 0xffff : a;是答案。我喜欢你的答案，因为表面上看起来它不会在任何明智的实现中分支（除非因为某些巧妙的优化）。因此，在应用程序的“可移植性”部分中可以将其保留，作为在将其移植到新平台时与NORMAL进行测试的东西，在编写完全特定于平台的代码（可能是汇编）之前。 - Steve Jessop

Answer 3

首先，“非分支方法”这个词组在讨论C代码时从技术上讲并没有意义；优化器可能会找到从“有分支”的C代码中删除分支的方法，反之亦然，它完全有权利用分支替换你聪明的非分支代码，只是为了恶意挑衅你（或者因为某些启发式算法认为这样做更快）。

除此之外，这个简单的表达式：

uint16_t b = a > UINT16_MAX ? UINT16_MAX : a;

尽管“有分支”，但在许多系统上，许多编译器都会将其编译为某种（无分支）条件移动（或可能仅是饱和）。 我刚刚尝试了ARM和Intel的三个不同编译器，所有编译器都生成了一个条件移动。

我会使用那个简单易读的表达式。 当且仅当您的编译器不足以优化它（或您的目标架构没有条件移动），并且如果您有基准数据表明这对您的程序是瓶颈，那么我会（a）找到更好的编译器和（b）针对您的编译器提交错误报告，然后再寻找聪明的技巧。

如果您真正致力于过于聪明一半，那么 ruslik 的第二个建议实际上非常美丽（比通用的min/max好多了）。

- Stephen Canon

Answer 4

1) 在 CPU 上有一种本地执行此类转换的内在功能。

2) 你可能不会喜欢这个，但是：

c = a >> 16; /* previously declared as a short */
/* Saturate 'c' with 1s if there are any 1s, by first propagating
1s rightward, then leftward. */
c |= c >> 8;
c |= c >> 4;
c |= c >> 2;
c |= c >> 1;
c |= c << 1;
c |= c << 2;
c |= c << 4;
c |= c << 8;
b = a | c; /* implicit truncation */

- Karl Knechtel