数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究C++ 中的位操作（重要技巧）
让我们首先回顾一下关于位和位运算符的简要信息。
位是二进制数字。它是计算机可以理解的最小数据单元。它只能具有两个值之一：0（表示关闭）和 1（表示开启）。
位运算符是在程序中按位操作的运算符。
这些运算符用于操作程序中的位。
在 C 中，我们有 6 个位运算符：
按位与 (&)
按位或 (OR)
按位异或 (XOR)
按位左移 (<<)
按位右移 (>>)
按位取反 (~)
https://tutorialspoint.com/cprogramming/c_bitwise_operators.htm
现在，让我们学习一些重要的技巧，即如果您使用位，可能会对您有所帮助的内容。
交换两个数字（使用按位异或）
我们可以使用按位异或运算符交换两个值。实现如下：
示例
#include <stdio.h>
int main(){
int x = 41;
int y = 90;
printf("Values before swapping! \n");
printf("x = %d \t", x);
printf("y = %d \n", y);
x = x ^ y;
y = y ^ x;
x = x ^ y;
printf("Values after swapping! \n");
printf("x = %d \t", x);
printf("y = %d \n", y);
return 0;
}输出
Values before swapping! x = 41 y = 90 Values before swapping! x = 90 y = 41
有效查找 MSB（最高有效位）的方法
对于任何整数值，我们都可以找到最高有效位，这是一个有效的方法。这是使用或运算符以及按位移位运算符完成的。此方法可以在 o(1) 时间复杂度内找到 MSB。
整数的大小应预定义以创建程序。
示例
查找 32 位整数 MSB 的程序：
#include <stdio.h>
int findMSB(int x){
x |= x>>1;
x |= x>>2;
x |= x>>4;
x |= x>>8;
x |= x>>16;
x = x+1;
return(x >> 1);
}
int main(){
int x = 49;
printf("The number is %d\n", x);
int msb = findMSB(x);
printf("MSB of the number is %d\n", msb);
}输出
The number is 49 MSB of the number is 32
直接计算从 1 到 n 的所有数字的异或。
如果我们仔细观察 0 到 n 的异或，我们可以推导出一个通用模式。这里说明了：
示例
#include <stdio.h>
// Direct XOR of all numbers from 1 to n
int findXORuptoN(int n){
switch( n%4){
case 0: return n;
case 1: return 1;
break;
case 2: return n+1;
break;
case 3: return 0;
break;
default: break;
}
}
int main(){
int n = 9870;
int xorupton = findXORuptoN(n);
printf("XOR of all number up to %d is %d\n", n, xorupton);
}输出
XOR of all number up to 9870 is 9871
直接计算与一个数字小于或等于一个数字的组合总数，其和与异或相等。
使用按位移位运算符，我们可以轻松完成工作，并且需要更少的时间。
示例
#include <stdio.h>
int countValues(int n){
int unset=0;
while (n){
if ((n & 1) == 0)
unset++;
n=n>>1;
}
return (1<<unset);
}
int main(){
int n = 32;
printf("%d", countValues(n));
}输出
32
查找整数中前导零和尾随零的个数
由于位操作，有一些内置方法可以找到整数的前导零和尾随零的个数。
* 这是一个 GCC 内置函数
示例
#include <stdio.h>
int main(){
int n = 32;
printf("The integer value is %d\n", n);
printf("Number of leading zeros is %d\n", __builtin_clz(n));
printf("Number of trailing zeros is %d\n",__builtin_clz(n));
}输出
The integer value is 32 Number of leading zeros is 26 Number of trailing zeros is 26
检查数字是否为 2 的幂？
要检查数字是否为 2 的幂，可以使用位运算符轻松实现。
示例
#include <stdio.h>
int isPowerof2(int n){
return n && (!(n&(n-1)));
}
int main(){
int n = 22;
if(isPowerof2(n))
printf("%d is a power of 2", n);
else
printf("%d is not a power of 2", n);
}输出
22 is not a power of 2
查找集合所有子集的异或
这可以通过以下事实来完成：如果有多个元素，则所有子集的异或始终为 0，否则为该数字。
示例
#include <stdio.h>
int findsubsetXOR (int set[], int size){
if (size == 1){
return set[size - 1];
}
else
return 0;
}
int main (){
int set[] = { 45, 12 };
int size = sizeof (set) / sizeof (set[0]);
printf ("The XOR of all subsets of set of size %d is %d\n", size,
findsubsetXOR (set, size));
int set2[] = { 65 };
size = sizeof (set2) / sizeof (set2[0]);
printf ("The XOR of all subsets of set of size %d is %d\n", size,
findsubsetXOR (set2, size));
}输出
The XOR of all subsets of set of size 2 is 0 The XOR of all subsets of set of size 1 is 65
将给定的二进制数字转换为整数
C 中的auto关键字用于执行此任务。
示例
#include <stdio.h>
int main (){
auto integer = 0b0110110;
printf("The integer conversion of binary number '0110110' is %d", integer);
}输出
The integer conversion of binary number '0110110' is 54
翻转数字的所有位
我们可以通过从一个所有位都设置的数字中减去它来翻转数字的所有位。
Number = 0110100 The number will all bits set = 1111111 Subtraction -> 1111111 - 0110100 = 1001011 (number with flipped bits)
示例
#include <stdio.h>
int main (){
int number = 23;
int n = number;
n |= n>>1;
n |= n>>2;
n |= n>>4;
n |= n>>8;
n |= n>>16;
printf("The number is %d\n", number);
printf("Number with reversed bits %d\n", n-number);
}输出
The number is 23 Number with reversed bits 8
检查位是否具有交替模式
使用按位异或运算，我们可以找到数字的位是否处于交替模式。以下代码展示了如何操作：
示例
#include <stdio.h>
int checkbitpattern(int n){
int result = n^(n>>1);
if(((n+1)&n) == 0)
return 1;
else
return 0;
}
int main (){
int number = 4;
if(checkbitpattern == 1){
printf("Bits of %d are in alternate pattern", number);
}
else
printf("Bits of %d are not in alternate pattern", number);
}输出
Bits of 4 are not in alternate pattern
更新于：2020-08-05
3K+ 浏览量
广告