bitwise-operators - 我应该使用哪些位移技术？

Question

我很想知道人们为自己建立了哪些使用模式，以便在客户端/服务器、Web、桌面开发等现代环境中利用位移。除了设备驱动程序、asm 之外，在软件开发中位移位的用途是什么？

我应该使用哪些按位运算/移位技术？我可以重用哪些算法？

score 3 · Accepted Answer

这实际上取决于您开发的语言、应用程序等。话虽如此，我会看看Hacker's Delight。我想它会有你正在寻找的东西。

score 3 · Accepted Answer

最近发现，基本上每个现有的库二进制搜索在找到一个非常大的数组的中点时都会出现溢出错误。正如在 Java 中实现的那样，该修复使用右移而不是除法。见这篇文章。

score 2 · Accepted Answer

如今，按位运算的主要用途必须是标志字。（或者也许只是我？:-) 这允许您使用一个整数变量以紧凑而有效的方式存储多个布尔值。为此，您不使用移位，只使用 AND 和 OR 操作来测试和设置不同的位值。这通常可以用来使代码更高效（传递一个 32 位整数而不是 32 个布尔数组作为参数；在单个按位操作中设置/清除/切换/测试任意一组标志等）

另一个常见用途是将数据压缩成更紧凑的格式（常见于通讯、文件格式和内存紧张的嵌入式控制器等应用程序）。例如，如果您有一个介于 0 和 25 之间的数字，那么您可以将其存储在 5 位中（这足以存储值 0..31），而不是使用字节（8 位）或 int（通常32 位或更多）。

在某些架构/编译器上，您可以通过将乘法/除法操作替换为位移和加法的组合来加速操作 - 但如果大多数现代编译器发现有机会这样做，他们会为您执行此操作。例如，如果您使用优化编译器，“a *= 2”很可能会转换为“a <<= 1”。

然后有一些新颖的用途有时会很方便（参见另一个答案中已经提到的 Hackers Delight）。

如果您只是在做 Windows 窗体或 Web 类型的应用程序，那么使用按位运算的必要性可能不会很大，但即使在这些高级环境中，您也可以在某些情况下使用按位运算来使事情更清洁并且更有效率。或者至少让自己感觉不像水管工，更像工匠:-)

score 2 · Accepted Answer

我可以想到进行位移操作的 3 个原因：

一，作为进行整数乘法和除法的另一种方法。左移1位相当于乘以2；右移 1 位相当于除以 2。我很少这样做，因为它使代码更难阅读和理解，从而获得较小的性能改进。如果您要乘以或除以常数，一些编译器足够聪明，可以为您执行此操作，在这种情况下增益为零。这些天我唯一一次使用这种技术是在计算密集型的事情上。如果我正在编写一个对无限级数的许多项进行大量评估的数学库——比如评估对数和正弦——我可能会使用这样的东西。否则，以我的拙见，这不值得为下一个程序员感到困惑而付出代价。

二，结合ANDs和ORs，作为将多个逻辑字段打包成单个字段的一种方式。假设您有一个字段，其可能值的范围是 0-3，另一个是 0-7。第一个可以容纳 2 位，第二个可以容纳 3 位。因此您可以将两者打包成一个字节。您可以使用以下代码将它们放入：

byte b=(f1<<3) | f2;

你可以用以下方法把它们弄出来：

f2=b & 0x07;
f1=(b>>3) & 0x03;

在过去的美好时光里，当我使用 6kB 内存的计算机时，我做了很多这样的事情来将我需要的所有数据塞进内存中。今天，当我的桌面上有一个千兆字节而服务器上有多个千兆字节时，这样做的额外复杂性——阅读“更多出错的地方”——使得它不值得。如果您正在为手机或其他一些内存非常受限的环境编写嵌入式代码，也许您仍然需要做这样的事情。我想如果你正在从事一个需要大量内存数据的项目——如果你正在分析人类基因组或其他东西——这可能是必要的。不过，在大多数情况下，知道如何做到这一点就像知道如何使用计算尺一样：这是一个有趣的历史遗迹，在今天几乎没有实用价值。

三、在读取或写入磁盘时数据类型之间的转换，或与具有不同数据存储格式的另一个系统通信。例如，假设您想将一个 4 字节的二进制数写入磁盘。您知道某些读取此文件的计算机首先存储具有最高有效字节的整数，而其他计算机则首先存储具有最低有效字节的整数。为确保两者都能正确读取数据，您必须以一致的方式存储和检索数据。所以你选择一个字节顺序并强制它以这种方式存储。像：

for (int p=0;p<4;++p)
{
  byte b=i & 0xff;
  out.write(b);
  i=i>>8;
}

这是我这些天唯一一次使用位移。

score 1 · Accepted Answer

这是我用来操作像素缓冲区的位移和掩码的巧妙应用。

bool pBuffer::GetPixel(unsigned int x, unsigned int y)

{

char c = blocks[((y * width) + x) / 8];

return (bool)((c >> (((y * width) + x) % 8) & 1));

}

宽度和高度是所谓的二维数组的已知尺寸。然而，数组 (blocks[]) 只是一维的。char 中的每一位代表一个像素，它是开还是关。

这个功能在我的凸包算法的实现中被使用，以允许用户使用最少的内存在屏幕上绘制 2D 级别。

关键是，如果您知道位是如何表示您的数据的，那么您可以通过位移对这些数据做一些偷偷摸摸的事情。

score 1 · Accepted Answer

1

我猜计算机编程的艺术，卷。四，Fasc。1就在你的小巷里。

于 2009-10-20T13:53:51.233 回答

score 1 · Accepted Answer

它们对于位掩码枚举非常有用，例如

  enum flags {
    IMAGE_FLIP_HORIZONTAL   =1 << 0,
    IMAGE_FLIP_VERTICAL     =1 << 1,
    IMAGE_DESATURATE        =1 << 2,
    IMAGE_INVERT            =1 << 3,
    IMAGE_NOALPHA           =1 << 4 
  };

然后你可以提供一个 API 允许

loadImage("pirate.gif", IMAGE_DESATURATE | IMAGE_FLIP_HORIZONTAL);

如果您曾经使用过 libpng，那么您可能会使用这种类型的枚举。在 pngread.c 文件末尾有一个块，它使用这样的掩码来应用转换：

#if defined(PNG_READ_INVERT_SUPPORTED)
   /* invert monochrome files to have 0 as white and 1 as black
    */
   if (transforms & PNG_TRANSFORM_INVERT_MONO)
       png_set_invert_mono(png_ptr);
#endif

#if defined(PNG_READ_BGR_SUPPORTED)
   /* flip the RGB pixels to BGR (or RGBA to BGRA)
    */
   if (transforms & PNG_TRANSFORM_BGR)
       png_set_bgr(png_ptr);
#endif

#if defined(PNG_READ_SWAP_ALPHA_SUPPORTED)
   /* swap the RGBA or GA data to ARGB or AG (or BGRA to ABGR)
    */
   if (transforms & PNG_TRANSFORM_SWAP_ALPHA)
       png_set_swap_alpha(png_ptr);
#endif

#if defined(PNG_READ_SWAP_SUPPORTED)
   /* swap bytes of 16 bit files to least significant byte first
    */
   if (transforms & PNG_TRANSFORM_SWAP_ENDIAN)
       png_set_swap(png_ptr);
#endif

score 0 · Accepted Answer

从“现代”的角度来看，位转换？不...除非您使用 C 或需要极其优化您的应用程序。
首先，位移可以用于两件事：

作为乘法/除法的快速替代方案，或在不能乘法/除法的架构上（请看下面的示例）
作为获取位域值的实用程序 ( EVIL )

位移 1 相当于除以 2 或乘以 2，而且速度更快。自己检查一下：64>>1==32和64<<1==128。事实上，软件乘法/除法的实现通常基于班次。

附言。好的。这只是我的意见。我知道位域是你儿时的朋友，但拜托，这只是一种意见。

bitwise-operators - 我应该使用哪些位移技术？

8 回答 8

Related

Reference