0

我不熟悉按位运算。我有这个序列：

1 0 0 0 0 : 16
---------------
0 1 1 1 1 : 15
---------------
0 1 1 1 0 : 14
---------------
.
.
.
---------------
0 0 0 1 1 :  3
---------------
0 0 0 1 0 :  2
---------------
0 0 0 0 1 :  1
---------------

我想先检查是否有多个“1”。如果是这种情况，我想删除具有较大十进制值的那个，并完成，获得更大的剩余。例如15，有四个“1”，我删除了较大的一个，“1”在“8”处，我得到“0 0 1 1 1 : 7”，其中较大的“1”在“4”处。我怎样才能做到这一点？

4

2 回答 2

1

这是执行您想要的代码：

unsigned chk_bits(unsigned int x) {
    unsigned i;
    if (x != 0 && (x & (x-1)) != 0) {
        /* More than one '1' bit */
        for (i = ~(~0U >> 1); (x & i) == 0; i >>= 1)
            ; /* Intentionally left blank */
        return x & ~i;
    }
    return x;
}

请注意，我假设您正在处理无符号数字。这通常更安全，因为右移是在有符号整数上定义的实现，因为符号扩展。

该if语句检查 . 中是否设置了多个位x。是一种已知的获取与关闭第一个“1”最低有效位x & (x-1)相同的数字的方法（例如，如果是，那么是。因此，说：xx101100100x & (x-1)101100000if

如果 x 不为零，并且如果关闭第一个设置为 1 的位（从 LSB 到 MSB）导致不为 0，那么...

这相当于说在x.

然后，我们遍历 中的每一位x，在设置的第一个最高有效位处停止。i被初始化为1000000000000000000000000000，并且循环一直向右移动它，直到x & i计算出不为零的值，此时我们找到了第一个最高有效位1. 此时，取i' 的补码将产生关闭 中该位的掩码x，因为~i除了唯一的位是 a 1（对应于 中的最高位x）之外，每个位都设置为 1 的数字。因此，与此相加可以x为您提供所需的内容。

该代码是可移植的：它不假定任何特定的表示，也不依赖于unsigned32 位或 64 位这一事实。

更新：阅读您的评论后，我将添加更详细的解释。

第一步 - 了解做什么x & (x-1)：

这里我们必须考虑两种可能性：

  • x以 1 ( .......0011001)结尾
  • x以 0 ( .......0011000)结尾

在第一种情况下，很容易看出它x-1只是x将最右边的位设置为 0。例如，0011001 - 1 = 0011000，因此，实际上，x & (x-1)将只是x-1。

在第二种情况下，可能会稍微难以理解，但如果最右边的位x是 0，则将x-1每个x0 位切换为 1 位，从最低有效位开始，直到找到 1，这变成了0。

让我举个例子，因为这对于新手来说可能很棘手：

1101011000 - 1 = 11101010111

这是为什么？因为以0结尾的二进制数的前一个数字是一个二进制数，在最右边的位置填充了一个或多个1位。当我们增加它时，例如10101111101111 + 1，我们必须增加下一个“空闲”位置，即下一个 0 位置，以将其变为 1，然后该位置右侧的所有 1 位都变为 0 . 这是任何base-n计数的工作方式，唯一的区别是base-2你只有0和1。

想想以 10 为底的计数是如何工作的。当我们用完数字时，值会回绕，我们在左侧添加一个新数字。之后是什么999？好吧，计数再次重置，左边有一个新数字，9 环绕到 0，结果是1000。二进制算术也会发生同样的事情。

想想二进制计数的过程；我们只有 2 位，0 和 1：

  • 0（十进制 0）
  • 1（十进制1 - 现在，我们用完了位。对于下一个数字，这个1将变成0，我们需要在左边添加一个新位）
  • 10（十进制 2）
  • 11（十进制 3 - 该过程将再次重复 - 我们用完了位，所以现在这 2 位将变为 0，并且必须在左侧添加一个新位）
  • 100（十进制 4）
  • 101（十进制 5）
  • 110（同样的过程再次重复）
  • 111
  • ...

看看模式和我描述的完全一样吗？

请记住，我们正在考虑第二种情况，其中x以 0 结尾。与 比较x-1时x，最右边的 0x现在是 1 x-1，最右边的 1x现在是 0 x-1。因此，唯一x保持不变的部分是 1 左侧变成 0 的部分。

因此，直到第一个最右边的 1 位所在的位置之前，x & (x-1)将是相同的。x所以现在我们可以看到，在这两种情况下，x & (x-1)实际上都会删除x.

第二步：到底是~0U >> 1什么？

字母U代表unsigned。在 C 中，整数常量是类型int，除非您指定它。将 a 附加U到整数常量使其无符号。我使用它是因为，正如我之前提到的，右移是否进行符号扩展是由实现定义的。一元运算符~是补码运算符，它抓取一个数字，并取其补码：每个 0 位都变成 1，每个 1 位都变成 0。所以，~0 是一个用 1 填充的数字：11111111111...。然后我将它向右移动一个位置，所以现在我们有了: 01111111....，这个表达式是~0U >> 1。最后，我取它的补码，得到100000....代码中的~(~0U >> 1). 这只是一种可移植的方式来获取一个最左边的位设置为 1 并且每隔一个设置为 0 的数字。

您可以查看 K&R 第 2 章，更具体地说，第 2.9 节。从第 48 页开始，介绍了按位运算符。练习 2-9 要求读者解释为什么x & (x-1)有效。如果你不知道，K&R 是一本描述 C 编程语言的书，由 C 的创造者 Kernighan 和 Ritchie 编写。书名是《The C Programming Language》，我建议你获得第二版的副本. 每个优秀的 C 程序员都从这本书中学习了 C。

于 2013-11-04T10:53:27.887 回答
0

我想先检查是否有多个“1”。

如果一个数字1在其二进制表示中有一个，那么它就是一个可以用 2 x形式表示的数字。例如，

4 00000100 2^2  
32 00010000 2^5

所以要检查单个，你可以只检查这个属性。

如果 log 2 ( x ) 是一个整数，那么1它的二进制表示中只有一个。

您可以计算log 2 ( x )

日志2 ( x ) = 日志y ( x ) / 日志y (2)

其中y可以是任何东西，对于标准日志函数来说是 10 或e。

这是一个解决方案

double logBase2 = log(num)/log(2);   
if (logBase2 != (int)logBase2) {

    int i = 7;
    for (;i >0 ; i--) {

        if (num & (1 << i)) {

            num &= ~(1 << i);
            break;
        }
    }
}

于 2013-11-04T05:31:54.060 回答