位运算解释

• 下载源码 - 2.76 KB

背景

在阅读了 PJ Arends 的精彩文章《按位运算符入门》后，我想将这个场景进一步扩展，并分享一些我在实际生活中遇到过的按位运算的常见用法。上面提到的文章确实是本文的前提。

按位运算用起来确实是一种乐趣。如果谨慎使用，它们能让代码既美观又高效。

Using the Code

那么，让我们从 Denis Ritchie 提出的一个经典问题开始：“你有一个可用的变量（例如 int），你需要找出其二进制表示中有多少位是设置为 1 的。”

假设你声明了一个 int var = 13，那么 var 的二进制结构将是：

512	256	128	64	32	16	8	4	2	1
0	0	0	0	0	0	1	1	0	1

阴影单元格表示每个“桶”的权重，在高位，所有“桶”都实际存在，但我们在示例中忽略了它们。现在，让我们编写一个函数来返回这个变量中设置的位数。

int __numOf_SET_Bits(int var){
 if (var==0) return 0;
 else return (var&01)?1+__numOf_SET_Bits(var>>1):__numOf_SET_Bits(var>>1);
}

这是一个简单的递归函数，用于计算变量二进制表示中设置的位数总数。函数的核心是两个按位运算：

1. 第一个是通过与 1 进行按位 AND 来检查最右边的位是否为 1，如果是，则总数加一。
2. 在递归调用函数时，将变量右移 1 位，从而截断最右边的位（最左边的位将被零填充）。

这个算法也有一个迭代版本，请参考 Denis Ritchie 的《C 编程语言》一书。

好的，现在让我们分析另一个类似的问题：“判断一个数字是偶数还是奇数”。朴素的算法是：

#define isEven(a) \
  ((((a)%2)==0)?1:0)

但如果你仔细观察任何变量的二进制模式，你会发现除了最右边的位（权重为 1）之外，所有位的权重都是偶数。现在，因为（偶数 + 偶数）= 偶数，并且（偶数 + 奇数）= 奇数，我们可以得出结论：对于偶数，最右边的位必须为零；对于奇数，最右边的位必须设置为 ONE。所以，让我们尝试根据这个属性编写一个函数/宏：

#include <stdio.h>
#define isEven(a) \
  ((((a)&01)==0)?1:0)
int main()
{
 int var=1;
 if(isEven(var)){
    printf("%d is a even number \n",var);
 }
 else
    printf("%d is a odd number \n",var);
 return 0;
}

哇，这个看起来很酷。

现在，让我们分析另一个问题：“判断一个数字是否是 2 的幂”。即，所有数字 1、2、4、8、16、32、64、128…… 都是 2 的幂。如何找出这一点？我将给出两个解决方案。

如果你仔细观察二进制模式，所有 2 的幂的数字都有一个设置为 1 的位，其余位都为零。现在，如果我们对该数字进行按位 AND 操作，使其减去 1，那么操作结果将为零。以 128 为例：

数字	128	64	32	16	8	4	2	1
128	1	0	0	0	0	0	0	0
128-1=127	0	1	1	1	1	1	1	1
128 按位 AND 127	0	0	0	0	0	0	0	0

好了，我们确实可以利用这个属性。让我们编写第一个版本的代码：

#include <stdio.h>
#define __isPower_of_TWO(a) \
 (((a)&(a-1))==0)?1:0
int main(){
 int arr[] = {1,2,3,4,5,8,9,16};
 int i=0;
 for(;i<sizeof(arr)/sizeof(arr[0]);i++){
        if (__isPower_of_TWO(*(arr+i)))
           printf("%d has a form of Power of Two \n",*(arr+i));
        else
           printf("%d is not in the form \n", *(arr+i));
 }
 return 0;
}

现在考虑另一种方法：

#include <stdio.h>
#define __isPower_of_TWO(a) \
 (((a)&(-a))==a)?1:0
int main(){
 int arr[] = {1,2,3,4,5,8,9,16};
 int i=0;
 for(;i<sizeof(arr)/sizeof(arr[0]);i++){
        if (__isPower_of_TWO(*(arr+i)))
           printf("%d has a form of Power of Two \n",*(arr+i));
        else
           printf("%d is not in the form \n", *(arr+i));
 }
 return 0;
}

这确实是完成同一工作的另一种好方法。

现在让我们看一个不使用第三个变量来交换两个变量值的著名问题。朴素的算法使用算术运算符来完成此操作。更巧妙的方法是使用按位 XOR 运算，XOR 运算有一个独特的属性：当位值相同时（都是零或都是一），返回 0；当位值不同时（一个为零，一个为一），返回 1。让我们先写出逻辑，然后举例说明。

#include <stdio.h>
void __SWAP(int *a,int *b){
 *a = *a ^ *b;
 *b = *a ^ *b;
 *a = *a ^ *b;
}
int main()
{
 int a=5, b=6;
 printf("Before swap: a=%d <=====> b=%d \n",a,b);
 __SWAP(&a,&b);
 printf("After  swap: a=%d <=====> b=%d \n",a,b);
 return 0;
}

在逻辑的核心，有三个连续的按位 XOR 操作，它们依次交换值。太棒了，我们来看一个例子。

最初 a 和 b 的二进制模式是：

a	0	0	0	0	0	1	0	1
b	0	0	0	0	0	1	1	0

现在，在第一次按位 XOR 操作后，a 和 b 的值变为：（仅检查 a 的二进制模式会改变，“b”在此步骤中保持不变。（\* 表示哪个位改变了状态）。

a	0	0	0	0	0	0 (*)	1 (*)	1
b	0	0	0	0	0	1	1	0

第二次操作后：（这里只有“b”会被改变，并且检查 b 的二进制模式现在包含 a 的原始二进制模式，因此 a 的值已移到 b 中）。

a	0	0	0	0	0	0	1	1
b	0	0	0	0	0	1	0 (*)	1 (*)

第三次操作后：（这里只有 a 的值会改变，看！b 的值已移到 a 中，交换操作成功了）。

a	0	0	0	0	0	1 (*)	1	0 (*)
b	0	0	0	0	0	1	0	1

现在，让我们分析一种数据结构构建技术，称为“XOR 链表”。双向链表是一种数据结构，其中每个节点包含一个数据成员以及指向列表中前一个和后一个元素的两个指针。对于列表中的最后一个节点，“next”的值为 NULL；对于第一个节点（head），“prev”的值为 NULL。如果 head 本身包含 NULL，则列表为空。由于每个节点包含两个地址部分（一个用于前驱，一个用于后继），存储需求会增加。按位 XOR 操作可以将相同的信息压缩到一个地址字段中。

考虑以下代码：

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef struct XOR_based_Node {
 int data;
 unsigned long compressedAddress;
}node;
node* head = NULL;
void add_element_to_list(node** headRef, int data)
{
  node *newNode = (node*)malloc(sizeof(node));
 assert(newNode);
 newNode->compressedAddress = (unsigned long)(*headRef);
 newNode->data = data;
 if(*headRef != NULL)
  (*headRef)->compressedAddress ^= (unsigned long)newNode;
 *headRef=newNode;
}
void printList(node* head)
{
  unsigned long prev = 0;
 while(head) {
  unsigned long next = prev ^ head->compressedAddress;
  printf("%d ", head->data);
  prev = (unsigned long)head;
  head = (node *)next;
 }
 printf("\n");
}
int main(void) {
 int i=0;
 for(;i<10;i++)
   add_element_to_list(&head,i);
 printList(head);
 return 0;
}

在此代码中，所有地址计算都在一个地址字段（我们每个节点都有）中完成。此字段是在我们尝试使用按位 XOR 操作将节点推入列表时计算的，并且也使用按位 XOR 操作获取了正确的内存位置。

下面是输出：

bash-3.2$ gcc -g -o hello XoR_List.c 
bash-3.2$ ./hello
9 8 7 6 5 4 3 2 1 0 
bash-3.2$

结论

按位运算的实际生活示例不胜枚举。在文章的第二部分，我将重点关注数据结构（堆、优先队列、红黑树、伸展树），并尝试解释按位运算如何能极大地帮助我们实现它们。

参考文献

1. 《C 编程语言》作者：Denis Ritchie

历史

• 2008 年 8 月 19 日：初始发布