6

我看过什么是位移（位移）运算符以及它们是如何工作的？，但我仍然觉得位移的概念很难理解。

有人可以指出我在 C 中移位的更基本指南的方向吗？我希望它会很长，因为它需要涵盖整个主题。

我正在学习C 编程语言(AKA K&R)，这就是它的用途，所以我可以做练习。我了解基础知识，但我仍然无法进行正确的位移操作。

以下是让我难过的 K&R 的练习

练习 2-6：编写一个函数 setbits(x, p, n, y) 返回 x，其中从位置 p 开始的 n 位设置为 y 的最右边 n 位，其他位保持不变。

练习 2-7：编写一个函数 invert(x, p, n)，它返回 x，其中从位置 p 开始的 n 位反转（即 1 变为 0，反之亦然），其他保持不变。

练习 2-8：编写一个函数 rightrot(x, n)，返回整数 x 向右旋转 n 位的值

练习 2-9：在二进制补码系统中，x &= (x-1) 删除 x 中最右边的 1 位。解释原因，并使用此观察来编写更快的 bitcount 版本。

这些是 k&R（C 编程语言）书中的练习。这是最好的 C 书籍，但我无法理解位移，所以我在这些练习中遇到了问题。

4

8 回答 8

7

位移就是它的字面意思：向左或向右移动给定序列中的所有位。

您需要记住的是，每个十进制数（如 6、7、3、2）都表示为计算机内存中的位序列。因此，如果您在一段 C 代码中找到类似的内容：

(7 >> 1)

这意味着 7 的底层二进制表示中的位将右移 1 个位置。

我认为您引用的链接中的解释非常清楚。也许自己在纸上写下一系列位并按照引用的链接进行操作会有所帮助。

或者您可能还不了解计算机如何在内部处理数字。在这种情况下，在学习位移之前，您需要阅读相关内容。

于 2009-01-14T15:09:54.367 回答
3

您将需要更多工具包中的工具来回答这些问题，而不是转移。

我认为你需要开始非常基本的关于如何用二进制表示数字。然后，您将需要考虑如何设置和清除该数字中的特定位，或同时清除一组位。您需要知道如何测试以查看是否设置了某组位以及如何进行屏蔽。您必须能够使用按位运算符和、或、异或、反转等运算符来完成上述所有操作。

然后你会想知道移位——将位向左和向右移动特定数量的空格。您会想知道“空”的位会发生什么。它是用 1 还是 0 填充的？什么时候用 1 或 0 填充？

谷歌搜索“按位运算教程”似乎已经提出了一些有希望的结果。但是这里有一些基础知识可以用来测试你自己，以确保你理解

// 1234 in hexadecimal. Do you understand this is not 1234 in decimal? Do you understand
// how specifying in hex makes it easier to think about the binary representation?
unsigned short i = 0x1234;
// Flip all the bits in 0x1234
printf("%04x", ~i);

// Test - Is the most significant bit set?
// mask is a binary number with the most significant bit set. Do
// you understand why this is so?
unsigned short mask = 0x8000;
if ((mask & i) == mask)
{
    printf("bit set!");
}
else
{
    printf("bit cleared!");
}

// Set the most significant bit
i = i | mask;
printf("Set the MSB of i, check it out: %i\n", i)

// Set the second most significant bit
// Do you see how by shifting mask right one it becomes the next most significant bit?
i = i | (mask >> 1);

祝你好运！

于 2009-01-14T15:58:54.657 回答
1

将这些位写在纸上，考虑从一端擦除它们，然后在另一端添加更多。与小学不同，乘以 10 时移动小数点。

您所有的 C 函数都将移入零。

所以

x = y << 3;

表示左移三位，右边的新位全为零。左边的三个位进入“位桶”：

x = z >> 2

丢失右边的两位并在左边添加两个零。

您会发现缺少的功能以及 K&R 练习的内容。在现有的处理器类型中，您拥有比 C 或任何其他高级语言更多的转换能力。

您具有旋转功能，其中从一端移位的位在另一端移位。

因此，以这种方式向右旋转一位的数字 0xD 将是 0xE，因为最低有效位是 1，因此将 1101 向右移动，右侧的 1 变为左侧的 1 1110。

有时您会通过ALU中的进位位进行轮换。假设进位位中有一个零，并且您将 0xD 旋转了一位 0 1101 留下 1 0110 a 0x6。再旋转一个，0 1011，你得到一个 0xB 等等。

你为什么要通过你问的进位位旋转？对于更大的数字，假设您有四个位寄存器并且想要进行 8 位移位，假设每个字母都是 bcde fghi 位，其中a是进位位，另外两组四位是四位寄存器。首先通过进位 e abcd fghi 循环左寄存器，然后通过进位 i abcd efgh 循环右寄存器。很酷；我们刚刚使用 4 位移位函数进行了 8 位移位。

如果您在开始之前清除了进位位（通常有此指令，或者您始终可以执行诸如添加 0+0 之类的操作或其他保证清除该位的操作），您将拥有

我 0bcd efgh

如果您说的是在 64 位数字上运行的 32 位指令集，这与 C 移位函数的作用没有什么不同。

处理器通常具有类似 C 的移位，其中一个零被移入，将 abcd 向左移动 1 得到 bcd0 将 abcd 向右移动 2 得到 00ab。

这给使用现代处理器的年轻人带来了一些问题……想想这些事情，因为他们的处理器都支持整数除法，并且可以在单个时钟周期内运行。早在我们进行除法之前，或者当除法是几十到几百个时钟时，但是移位是一个时钟，您可以使用移位来完成 2 次除法或乘法的所有功率。将数字 0x0D 左移 2 后得到 0b00001101 << 2 = 0b00110100 或 0x34。0xD 是十进制的 13，而 0x34 是十进制的 52。52 是 13 的四倍。四是 2 的 2 次方。移位 2 与乘以 4 相同。

这是双向的；0x34 右移 2 是 0xD，但这就是问题所在。当你得到负数时，将数字减去 4 0xFC，然后将其除以 2。使用 C 0xFC >> 1 将给出 0x7E，但 0x7E 是十进制的 +126。-4/2 = 126 怎么算？

问题是 C 在零处移动。您会发现某些处理器具有与逻辑移位不同的算术移位。算术移位保持最高位，所以如果你使用一个有符号数，比如 0bQWER，并且你算术右移一位，你会得到 0bQQwe。最高位都移动到下一位并保持在原来的位置。

再次移位 0bQQQW，以此类推。现在算术左移将移入零而不是最低有效位，因此 0bQWER 左移一位是 0bWER0。这是有道理的。-4 左移一位是 0xF8，即 -8，-4 乘以 2 是 -8，所以是正确的。

所以你会发现有些处理器只有算术右移，而没有左移。有些允许你指定一个 asl，但是当他们组装它时，用 lsl（逻辑左移）替换它，谁知道有些可能实际上有一个单独的操作码，即使它是相同的功能。我假设可能有一些有 asl 和 asr 和 lsr，但没有 lsl。

只需使用纸和铅笔并弄清楚事情。从实数作为例子开始，然后再抽象。想0x1234向右旋转一点，比方说？

0001001000110100  write out the bits
x0001001000110100 shift right one
0000100100011010  because this is a rotate fill in the new bit with the bit that fell off on the prior operation

现在想右移两位

0000100100011010
xx0000100100011010
1000001001000110

我将如何在 C 中进行一次旋转？

unsigned int rotate_right_one ( unsigned int x )
{
  unsigned int y;
  y = x & 1;  // Save the bit that is about to fall off the right
  x >> = 1;  // Logical rotate one bit
  x |= y<<31; // This assumes that unsigned int is 32 bits.
  return(x);
}

要旋转更多，您可以简单地多次调用此函数，或者考虑掩码并在上方移动，以及它如何工作超过一位。

另请注意，某些处理器只有一种旋转功能。例如，想想这个。我有一个四位寄存器，我旋转 5 位。我能得到什么？

abcd
bcda  first rotate
cdab  second
dabc  third
abcd  fourth
bcda  fifth

单向左旋转是什么样的？

abcd
bcda  one bit left.

四位寄存器上的右五与左一相同 5-4=1。与 asl 一样，一些处理器允许您对操作进行编码，但汇编器使用 nbits-shift 作为旋转量，用另一个旋转替换该操作。

对于某些人来说，逻辑位运算就像指针一样难以理解，但它是基础，如果您学习并使用它，您将领先于您的竞争对手或您周围的人。

这是一个计算某个变量中位数的示例：

for(count=0, r=1; r; r<<=1) 
    if(r&some_variable) 
        count++;

理解那行代码，你就可以很好地学习 C 和逻辑位操作。

于 2009-01-15T15:13:35.327 回答
1

以 2-6 为例，我使用了 17、4、3、15 的值。
所以：

x = 17 或 10001

p = 4

n = 3

y = 15 或 01111

使用我的示例数字，我们需要在这里做的是从 y (111) 中取出三个 ls 位并将它们从位置 4 开始插入到 x 中。这将给我们 11111 或 31。我们需要从 x 开始清除 3 位位置四，清除 y 中除最右边 3 位之外的所有位，将它们移动到位置四并将两个值相或。

第一个：将所有1向左移动n个位置〜0 << n = 1111111111111000

第二：将所有的放在最右边的 n 个位置 ~(~0 << n) = 0000000000000111

第 3 步：将这 n 个 1 位移动到位置 p，并从位置 p 开始将 n 位设置为零。~(~(~0 << n) << (pn)) = 1111111111110001

4th: 这个掩码用 x 清除 x 在位置 p = 10001 的 n 位

（我相信每个人都意识到我们所做的只是回到我们的起始编号，但我们必须这样做以便告诉程序我们想要从哪个位置开始，以及我们想要使用多少位. 如果 p 是 6 而 n 是 4 怎么办？）

接下来清除 y 中的所有位，除了最右边的 n 位：

第一个： ~(~0 << n) 将所有的放在最右边的 n 个位置。0000000000000111

2nd: y & ~(~0 << n) 选择y的最右边n位 0000000000000111

3rd: (y & ~(~0 << n)) << (pn) 将 y 的 n 位放在位置 p 0000000000001110 最后 OR 两个结果一起

0000000000010001 = 17

0000000000001110 = 7 或=

0000000000011111 = 31

结果变为：

返回 x & ~(~(~0 << n) << (pn)) | (y & ~(~0 << n)) << (pn);

如果这很难阅读，我很抱歉。我的格式化能力有些受限。（我确信这是我的错）我希望这会有所帮助，我一直坚持这个特定的练习很长一段时间，今天终于想出了这个解决方案，在看了这个帖子之后，所以我想我会发布正确的答案，并解释为什么它是正确的答案，这是我发现在我见过的许多答案中缺乏的东西。

于 2012-01-22T23:12:53.583 回答
0

让我们尝试 2-6，让您了解位操作的工作原理，然后看看它是否有意义。

int setbits( int x, int p, int n, int y )
{
    int bitmask = ~0, y_right = 0; 

    /* Ok, first let's get y's rightmost bits.
     * Take our bitmask, shift it left by n bits, leaving the least significant
     * n bits as 0. Then, flip the bitmask so the rightmost n bits become 1, and the
     * leftmost n bits become 0.
     *
     * Then, AND this bitmask with y, to yield y's n rightmost bits.
     */
    bitmask = ~( bitmask << n );
    y_right = bitmask & y;

    /*
     * Ok, now let's use y_right as our bitmask for x.
     * Shift y_right to the left to *begin* at position p.
     */
     y_right <<= p - n;
     x |= y_right;

     return x;
}

注意：以上可能完全不正确，因为我还没有测试过，但它应该给你一个不错的开始。

于 2009-01-14T22:03:18.120 回答
0

如果你有钱（和时间），就拿一份Hacker's Delight（Henry S. Warren 着）。它可能是最好的移位指南。它将带您完成简单的转变（和其他操作技术），一直到格雷码等等......

于 2009-01-14T16:00:46.900 回答
0

让我们做一个练习，作为示例。

练习 2-6：编写一个函数 setbits(x, p, n, y)，它返回 x，从位置 p 开始的 n 位设置为 y 的最右边 n 位，其他位保持不变。

让我们记住，最低有效位是位 0（位于位置 0）。

这是伪代码：

  1. 将 x 中的 p 到 p+n 位移动到位置 0 到 n。那就是你右移的地方。
  2. 准备一个位掩码，它将位 n 到最高位的任何内容变为 0。您可以为此使用查找数组（例如，0xFF 表示 n=8，0x7F 表示 7 等等），或者您可以在循环中使用设置位 0 和左移的组合。
  3. 将位掩码应用于xusing &。我们不关心的所有位x现在都是 0。
  4. 反转位掩码。我们现在在高端有一堆 1，在低端有一堆 0。我们要在 y 中更改的位在位掩码中都有 0。
  5. 使用 & 将位掩码应用于 y。我们将用 x 中的位替换的 y 中的所有位现在都设置为 0，我们不想更改的位保持不变。
  6. 通过组合 x 和 y 来设置我们想要在 y 中更改的位|。这是关键点——用笔和纸复习正在发生的事情。x 中在 (3) 中设置为 0 的位不会影响 y 中的相应位。x 中不受 (3) 影响的位将与 y 中的 0 组合（由于 step5 为 0），将结果位设置为它在 x 中的值。
于 2009-01-14T16:16:19.973 回答
0

请记住，几乎所有这些练习都有一个简单的解决方案，可以使用函数 int IsBitSet(int i, int n); 编写。int SetBit(int i, int n); << 和 >> 的组合。直接的解决方案几乎都是最坏的情况，但更容易实现和阅读。这有点像在加法方面实现乘法或在增量方面实现加法。

于 2009-01-14T17:09:39.600 回答