資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究C++ 中的位操作（重要技巧）
讓我們首先回顧一下關於位和位運算子的簡要資訊。
位是二進位制數字。它是計算機可以理解的最小資料單元。它只能具有兩個值之一：0（表示關閉）和 1（表示開啟）。
位運算子是在程式中按位操作的運算子。
這些運算子用於操作程式中的位。
在 C 中，我們有 6 個位運算子：
按位與 (&)
按位或 (OR)
按位異或 (XOR)
按位左移 (<<)
按位右移 (>>)
按位取反 (~)
https://tutorialspoint.tw/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+ 瀏覽量
廣告