bit-manipulation - 您是否曾经在实际项目中不得不使用位移位？

Question

您是否曾经在实际的编程项目中不得不使用位移位？大多数（如果不是全部）高级语言中都有移位运算符，但是你什么时候真正需要使用它们呢？

score 60 · Accepted Answer

我仍然为硬件中不支持浮点的系统编写代码。在这些系统中，几乎所有算术都需要移位。

您还需要轮班来生成哈希。多项式算术（CRC、Reed-Solomon 码是主流应用程序）或也使用移位。

然而，使用轮班只是因为它们很方便并且准确地表达了作者的意图。如果你愿意，你可以用乘法来模拟所有的位移，但这会更难写，更难读，有时更慢。

编译器检测可以将乘法简化为移位的情况。

score 38 · Accepted Answer

是的，我已经用过很多次了。位旋转在位掩码非常常见的嵌入式硬件上很重要。当您需要最后一点性能时，它在游戏编程中也很重要。

编辑：另外，我经常使用它们来操作位图，例如更改颜色深度或转换 RGB <-> BGR。

score 26 · Accepted Answer

为枚举创建漂亮的标志值（而不是手动输入 1、2、4...）
从位域中解包数据（许多网络协议使用它们）
Z 曲线遍历
性能黑客

我想不出很多使用它们的情况。它通常是另一种方式 - 存在一些特定问题，事实证明采用位操作将产生最佳结果（通常在性能方面 - 时间和/或空间）。

score 15 · Accepted Answer

我一直使用它们的一个地方是在为跨平台应用程序转置整数的字节顺序时。在对 2D 图形进行位图传输时，它们有时也会派上用场（与其他位操作运算符一起）。

score 9 · Accepted Answer

9

我已经使用过它们几次，但几乎总是用于解析二进制文件格式。

于 2009-02-06T15:13:01.933 回答

score 7 · Accepted Answer

位移很快。早在除法和模运算之前，它们就在 CPU 指令集中实现了。我们中的许多人都使用位移位进行算术，这在铅笔和纸上很简单，但在我们的 CPU 上不可用。

例如：

我在涉及将大型复合材料分解为其主要因素的项目中使用了位移。
我还使用位移来查找任意大整数的平方根和立方根。

score 5 · Accepted Answer

是的，仍然需要它。

例如，在我的工作中，我们开发了通过串行端口 COMx 与 PLC 通信的软件。需要处理一个字节内的位，我们每天使用左/右移位和逻辑运算符 OR、XOR、AND。

例如，假设我们需要打开一个字节的第 3 位（从右到左）：

00001001 -> 00001101

这样做效率更高：

Byte B;

B := B OR 4; //100

代替：

Byte B = 0;
String s;  // 0 based index

s = ConvertToBinary (B);
s[5] = "1";
B := ConvertToDecimal (s);

问候。

score 4 · Accepted Answer

是的，我有。您可能会怀疑它最有可能出现在低级编程中，例如开发设备的驱动程序。但是，我在一个 C# 项目中工作，我必须开发一个从医疗设备接收数据的 Web 服务。设备存储的所有二进制数据都被编码为 SOAP 数据包，但二进制数据被压缩和编码。所以要解压缩它，你必须做很多很多的位操作。此外，您必须进行大量位移才能解析出任何有用的信息，例如设备序列号是第二个字节的下半部分或类似的东西。我还看到 .NET (C#) 世界中的一些人使用位掩码和标志属性，我个人从未有过这样做的冲动。

score 4 · Accepted Answer

当我用汇编语言编写代码时，我的代码充满了位移和掩码。

在 C 语言中也做了相当多的事情。

在 JavaScript 或服务器语言方面做得不多。

可能最好的现代用途是逐步遍历表示为 1 和 0 的布尔值的打包数组。我过去总是左移并检查汇编中的符号位，但在高级语言中，你会与一个值进行比较。

例如，如果您有 8 位，则使用“if (a>127) {...}”检查最高位。然后你左移（或乘以 2），用 127 做一个“与”（或者如果设置了最后一位，则减去 256），然后再做一次。

score 3 · Accepted Answer

是的。我之前必须编写加密算法，并且肯定会使用它们。

当使用整数等来跟踪状态时，它们也很有用。

score 3 · Accepted Answer

我在图像压缩/解压缩中经常使用它们，其中位图中的位被压缩。使用http://en.wikipedia.org/wiki/Huffman_coding被压缩的东西由不同数量的比特组成（它们并非都是字节对齐的），因此在编码或解码它们时需要对它们进行位移.

score 3 · Accepted Answer

例如，在 C、C++ 等语言上的加密方法实现中。二进制文件、压缩算法和逻辑列表操作——按位操作总是好的 =)

score 3 · Accepted Answer

位移并不能解决高层次的编程问题，只是有时我们不得不解决低层次的问题，而且不用用 C 语言编写一个单独的库来做这件事很方便。那是它被使用最多的时候是我的猜测。

我亲自使用它来编写EBCDIC字符集转换器的编码器。

score 3 · Accepted Answer

3

将数字从小端格式转换为大端格式时，反之亦然

于 2009-02-06T15:41:19.787 回答

score 3 · Accepted Answer

我在一家计算机外围设备制造商工作。我几乎每天都遇到并且不得不实现使用位移的代码。

score 3 · Accepted Answer

移位在破译在线游戏的协议中被大量使用。这些协议旨在使用尽可能少的带宽，因此不是在 int32 中传输服务器上的玩家数量、名称等，而是将所有信息打包到尽可能少的字节中。如今，大多数人都使用宽带并不是真的有必要，但是当他们最初设计时，人们使用 56k 调制解调器进行游戏，所以每一点都很重要。

最突出的例子是 Valve 的多人游戏，尤其是 Counter-Strike、Counter-Strike Source。Quake3 协议也是相同的，但 Unreal 并没有那么苗条。

这是一个示例（.NET 1.1）

string data = Encoding.Default.GetString(receive);

if ( data != "" )
{
    // If first byte is 254 then we have multiple packets
    if ( (byte) data[0] == 254 )
    {
        // High order contains count, low order index
        packetCount = ((byte) data[8]) & 15; // indexed from 0
        packetIndex = ((byte) data[8]) >> 4;
        packetCount -= 1;

        packets[packetIndex] = data.Remove(0,9);
    }
    else
    {
        packets[0] = data;

    }
}

当然，您是否将其视为一个真正的项目或只是一个爱好（在 C# 中）取决于您。

score 2 · Accepted Answer

2

快速傅里叶变换——FFT和它的 Cooley-Tukey 技术将需要使用位移操作。

于 2009-02-06T15:16:03.347 回答

score 2 · Accepted Answer

求两个大于或等于给定数的最近幂：

1 << (int)(ceil(log2(given)))

需要在不支持任意纹理大小的硬件上进行纹理处理。

score 2 · Accepted Answer

另一个很常见的事情是在提取一个字节的高半字节时进行 4 位移位，即

#define HIGH_NIBBLE(byte) (((byte) >> 4) & 0x0F)
#define LOW_NIBBLE(byte)  ( (byte)       & 0x0F)

score 1 · Accepted Answer

1

是的，在 MPEG2-2 传输流解析器中使用它们。它更容易并且可读性更好。

于 2009-02-06T15:17:56.293 回答

score 1 · Accepted Answer

我不得不编写一个程序来解析 DVD 光盘上的 .ifo 文件。这些是解释光盘上有多少标题、章节、菜单等的文件。它们由各种大小和对齐方式的打包位组成。我怀疑许多二进制格式需要类似的位移。

score 1 · Accepted Answer

当多个标志用作属性参数时，我已经看到使用按位运算符。例如数字 4 = 1 0 0 表示设置了三个标志之一。这对公共 API 不利，但它可以在特殊情况下加快速度，因为检查位很快。

score 1 · Accepted Answer

1

如果没有左右滑动位的能力，我写过的每一个 bitblt-er 都无法完成。

于 2009-02-06T15:24:35.653 回答

score 1 · Accepted Answer

我在游戏中使用它们将一堆标志打包成一个字节/字符以保存到数据卡中。诸如存储可解锁状态等之类的东西。现在不是什么要求，但可以节省工作量。

score 1 · Accepted Answer

我在一个必须读取监视器的 EDID 数据的嵌入式系统项目中使用它。EDID 中的一些数据编码如下：

字节#3：
水平消隐——低8位
字节#4：
低半字节：水平消隐——高4位
高半字节：其他

score 1 · Accepted Answer

是的，在 Java 和 C# 应用程序之间执行二进制通信时，一种是 big-endian 字节顺序，另一种是 little-endian（不一定按此顺序）。我创建了一个 InputStream 类，它可以读取具有不同字节顺序的数字，并且它使用字节移位来工作。

有时，当您想在长的 4 个字节中放置 4 个短裤时，会出现使用字节移位的情况。我想我很多年前就这样做了...

score 0 · Accepted Answer

与“较低级别”设备、例如数字以太网 IO 盒或 PLC 通信时，也需要移位，这些设备通常将单个输入/输出值打包成字节。

score 0 · Accepted Answer

是的，移位一直用于低级嵌入式软件。它也可以用作执行极其快速的数学运算的魔术技巧，看看

http://betterexplained.com/articles/understanding-quakes-fast-inverse-square-root/

score 0 · Accepted Answer

是的，一直都是。就像这些用于将 3space 坐标与 32 位整数打包和解包的宏一样：

#define Top_Code(a, b, c)           ((((a) + x) << 20) | (((b) + y) << 10) | ((c) + z))                           
#define From_Top_Code(a, b, c, f)   (a = (((f) >>> 20) - x), b = ((((f) & 0xffc00) >>> 10) - y), c = (((f) & 0x3ff) - z))

score 0 · Accepted Answer

我曾经（很多很多年前）为一个使用 Excel Oper 结构创建 Excel 电子表格的项目编写了一个输出例程。这是一个二进制文件共振峰，需要大量的位旋转。以下链接提供了 Oper 结构Safari Books的风格。

score 0 · Accepted Answer

我在 C# 中做了一些位移。该应用程序需要标准化语音音频输入，这需要在音频样本级别进行多项数学运算。

score 0 · Accepted Answer

是的。特别是在使用硬件驱动程序的控制和状态字节的仿真器中。控制字节中的每一位都有特殊含义，状态字节中的每一位都有特殊含义。

score 0 · Accepted Answer

0

我在CRC计算中使用了它。

于 2009-02-09T15:32:36.743 回答

score 0 · Accepted Answer

当然。处理亲和力掩码使用位移位。

例如，您可能希望将应用程序限制为使用不超过给定数量的处理器（为使用每个处理器赚钱） - 您将使用位移来计算关联掩码中的位？

score 0 · Accepted Answer

我对新颖的加密结构做了一些工作，将序列化结构（以及对它们的后续更新）隐藏在同态加法器后面。很多哈希也依赖于位操作；在他们之间转移。

涉及大量位移和讨厌的大数运算；全部在 Java 中（诚然，这是一个参考/研究实现）。

还完成了压缩项目（特别是 GZIP impl），您需要非常频繁地打包位；无法想象没有 << 和 >>（或者 >>>，如果你在 Java 中的话）。

基本上，如果您正在使用加密或压缩，那么您很有可能需要在某一点或另一个点进行位移。

score 0 · Accepted Answer

不久前，我在一个 Web 项目中使用了位移。这是一个电子商务应用程序，其中每个产品都有许多可配置的属性。用户可以选择他们想要的属性，UI 会更新以提供所选选项的定价和 SKU。

不是在数据存储中搜索与用户选项匹配的 SKU，而是每个选项组合对应一个特定的哈希，这实际上是一个使用位数学创建的数字。我为每个选项允许 4 位（16 种组合），最多 5 个选项，所以总共 20 位。为了从用户的选项中计算哈希值，我将遍历每个编号属性并添加到哈希值：

for(var i = 0; i < getSku.arguments.length; i++)
{
    index = getAttributeIndex(i, getSku.arguments[i]);
    hash += (index+1) << (4*i);
}

这比遍历潜在的数百个 SKU 每次最多比较 5 个值要快得多。

score 0 · Accepted Answer

不，我从来没有真正需要使用它们。我认为这些二进制操作对于高级语言来说有点过时了。正如有人所说，它总是可以用其他数学表达式来模拟，并且由于这些几乎从未使用过，它们可以构建在外部库中。ruby 或 python 中的位移对我来说听起来很奇怪，有点像混合高电平和低电平。

score 0 · Accepted Answer

我在扑克手评估器中使用过它们。

扑克手表示为 64 位无符号整数，其中1每张牌对应一个位。通过移位和掩蔽的组合，您可以提出诸如“给我所有我手上至少有 3 张牌的等级”之类的问题。

它相当快，但我已经学会了更快的方法，其中手表示为字节数组。

score 0 · Accepted Answer

大多数数据包仍然是位编码的。如果您使用任何类型的低级网络通信，您将不得不使用比特。

还分析包含声音和视频的数据包——我相信即使是 MP3 标签也会使用一些位。

最重要的是，不习惯位操作意味着您很可能会错过实现某些操作的更好方法。我的意思是，如果您要处理 50 亿个有序对象的存在，那么能够非常舒适地将它们全部放入 ram 以进行即时查找或每次都在文件中查找它之间的区别——在这样的任务中我会说，一个自称是软件工程师，在没有位操作的情况下实现它的人不胜任他的工作。

score 0 · Accepted Answer

0

我用它来实现 UTF-8 和 UTF-32 之间的转换。

于 2010-06-09T05:29:48.007 回答

score 0 · Accepted Answer

是的。

移位在嵌入式应用程序中非常有用，因为内存很紧，速度就是一切。

例如，您可以只使用加法和位移来执行相同的计算，而不是进行昂贵的乘法运算，这样可以节省大量时间：

c := 0
while b != 0
    if (b and 1) != 0
        c := c + a
    shift a left by one
    shift b right by one
return c

score 0 · Accepted Answer

我正在计算机科学专业毕业，我已经使用了位移。

人们已经说过，它们可以很好地存储标志、处理哈希等。

我使用了一次按位运算将 1 个小整数（2 个字节）值和 2 个字符压缩到一个整数中。与我同事的项目相比，这为我节省了很多内存。

并且这些操作有时在算术上也非常快，例如，当您必须扩展 double 类型或使用函数来使用螳螂操作浮点数据时（请参阅浮点算术标准）。

bit-manipulation - 您是否曾经在实际项目中不得不使用位移位？

42 回答 42

Related

Reference