位元運算概述

以下帖子取自我創建的存儲庫，旨在幫助學習（和教授）按位運算。您可以在這裡找到該存儲庫，我建議您查看一下 - 那裡有一些程式碼範例和解決方案。

介紹

此儲存庫的目標是讓您熟悉位元運算，解釋它們是什麼、它們如何運作以及它們的用途。

第一章：一切都是二進位的

在 C（以及大多數高階語言）中，我們的變數具有 型別。這些類型表明了一些事情。當然，int 類型的變數將儲存整數值，但理解這些位元運算的關鍵是要知道，在幕後，所有類型都以二進位形式儲存在記憶體中（任何位置、堆疊、堆，無論何處）。以下是當您在 C:
中的堆疊上儲存簡單整數值時會發生的情況的範例

int main(int argc, char** argv) {
    int x = 2;
    return 0;
}

編譯為彙編後，程式碼可能如下所示（我這裡使用的是ARM彙編，並使用註解對程式碼進行了註解）：

.section .text
.global main

main:
    ; Set up the stack for the function
    stp x29, x30 [sp, -16]! ; Save previous frame pointer & link register
    mov x29, sp ; Setup a new frame pointer

    ; Initialize x with 2
    ; IN C: int x = 2;
    mov w0, 2 ; Move 2 into the w0 register
    str w0, [sp, 16] ; Store the contents of w0 (2) at a 16-byte offset from the stack pointer
    ; Essentially, the above line stores 2 on the stack.

    mov w0, 0 ; Move 0 into w0, prepare for return

    ; Clear stack
    ldp x29, x30, [sp], 32 ; Restore frame pointer and link register
    ret ; Return

請注意，大多數編譯器不會實際儲存像我在堆疊上顯示的那樣的變量，因為它未被使用。但是，如果多次使用，它會像上面一樣儲存在堆疊中。

如果我們查看變數在堆疊上儲存的位置（當然，它就在那裡），我們會看到類似以下內容：

Memory Address	Value Stored (Hex)	Value Stored (Binary)
0x1000	0x02	00000010
0x1001	0x00	00000000
0x1002	0x00	00000000
0x1003	0x00	00000000

這假設您的系統是小尾數法。我不會在這裡討論字節順序，但您可以在這裡閱讀更多相關資訊。

關於上表，我希望您注意的關鍵一點是，儘管我們的整數只有 2 位長，但它佔用了 4 個位元組（32 位元）的記憶體。現在，不要驚慌──這是正常現象，也是意料之中的。 C 和編譯器所做的許多事情之一就是為您呼叫的類型設定標準。因此，當我創建 int 變數時，編譯器知道分配 4 個位元組（同樣是 32 位元）記憶體。我們甚至可以使用 C 中的 sizeof() 運算子來測試這一點。

sizeof() 運算符

sizeof() 不是實際的 C 函數。相反，在編譯時，編譯器會將表達式替換為給定資料類型的大小。您甚至可以將其與您自己的類型一起使用，例如 typedef 和/或結構：

#include <stdio.h> 

typedef struct {
  char name[64];
  int age;
} Person;

int main(int argc, char** argv) {
  printf("A Person is %lu bytes long.\n", sizeof(Person));
  return 0;
}

您可能會問的另一件事是如何儲存負數。很好的問題。數字可以是有符號或無符號，但預設情況下，它們是有符號的。如果一個整數是有符號的，它將犧牲其最高有效位元作為「符號位」。如果符號位為1，則該數為負；否則它是正的。精明的讀者可能會意識到這裡發生的變化在可能的數字範圍內。考慮 8 位數字。有 256 個可能的數字可以表示（由 2^8 給出）。使用無符號8位元整數，可以表示0-255的值；使用有符號的 8 位元 int，可以表示 -128–127。

要取得二進位數的倒數，請使用二進位補碼。我們來求二進制的 -5。

1. 從5開始。在二進制中，5是0101。前導0是符號。
2. 反轉每一位。 0101→1010。
3. 將此數字加 1（忽略任何可能的溢位）。 1010 + 0001 = 1011.

輪到你了！

1. 透過對 -5 進行二進位補碼得到 5 或 0101，確認 -5 是二進位的 1011。
2. 寫一個 C 程序，以位元組和位元的形式列印 int 的大小。使用上面的程式碼作為起點。 提示：從位元組轉換為位，一個位元組有多少位？
3. 將不同類型的尺寸填入下表中，修改您的程式來檢查它們。

Type	Size (bytes)	Size (bits)
int
int64_t
int8_t
char
bool (you'll need to #include 7c6dd6636e138b73de36040ce8dc60d1)
long int
short int
long long int
double
double

Sample Responses

Question 1

1. Start with -5: 1011.
2. Invert each bit: 1011 → 0100.
3. Add 1: 0100 + 0001 = 0101

Question 2

Here's an example of what your simple program might look like (you can also check it out at Chapter 1/SizeOfOperatorTest.c).

 #include ade979de5fc0e1ca0540f360a64c230b

 int main(int argc, char** argv) {
    printf("The size of an int is %lu bytes, or %lu bits.\n", sizeof(int), sizeof(int) * 8);
    return 0;
 }

Go ahead and compile it using gcc and check out its output:

cd Chapter\ 1
gcc -o sizeof SizeOfOperatorTest.c
./sizeof

Question 3

Type	Size (bytes)	Size (bits)
int	4	32
int64_t	8	64
int8_t	1	8
char	1	8
bool (you'll need to #include 7c6dd6636e138b73de36040ce8dc60d1)	1	8
long int	4	32
short int	2	16
long long int	8	64
double	4	32
double	8	64

Take This Home

The main point I'd like you to keep in mind is that with control of every bit, we can optimize our memory usage. Though that has little effect on modern systems, in the case of embedded computing, every byte counts. By manually reading and writing bits as opposed to typical variable values, we can harness more functionality from less storage.

Chapter 2: Operating on Bits

Now that we've covered data types and how data is stored, we're ready to introduce the idea of bitwise operations. Put simply, a bitwise operation is an operation done on each bit of a piece of data. Let's take a look at each bitwise operator. Then, we'll implement them in C.

And (&)

Written x & y in C. This operator takes the corresponding bits of each number and performs an and operation. An and operation returns 1 (true) if and only if both bits are 1. This means that two bits that are both 0 do not return 1—they return 0. The result is the number made up of the binary string of results from each and. It's easiest to see this in a truth table.

Consider the operation int result = 3 & 5. First, convert 3 and 5 to binary.
Now, we have int result = 011 & 101. Consider the following truth table:

Bit A	Bit B	AND
0	1	0
1	0	0
1	1	1

The result of the and operation is 001, which when converted to decimal is 1.

Or (|)

Written x | y in C. This operator takes the corresponding bits of each number and performs an or operation. An or operation returns 1 if either bit is 1. As with other bitwise operators, the result is the number made up of the binary string of results from each or.

Consider the operation int result = 3 | 5. First, convert 3 and 5 to binary.
Now, we have int result = 011 | 101. Consider the following truth table:

Bit A	Bit B	OR
0	1	1
1	0	1
1	1	1

The result of the or operation is 111, which when converted to decimal is 7.

Xor (^)

Written x ^ y in C. This operator takes the corresponding bits of each number and performs an xor (exclusive or) operation. An xor operation returns 1 if and only if one of the two bits is 1. As with other bitwise operators, the result is the number made up of the binary string of results from each or.

Consider the operation int result = 3 ^ 5. First, convert 3 and 5 to binary.
Now, we have int result = 011 ^ 101. Consider the following truth table:

Bit A	Bit B	XOR
0	1	1
1	0	1
1	1	0

異或運算的結果是110，轉換成十進位後是6。

左移 (

寫x

考慮 int result = 5

初始

1	0	1

一班後

0	1	0

結果

1	0	0

二進位結果是100，十進位是4。

右移 (>>)

寫x>> amount 這個運算子就像左移一樣，只是它的工作方向相反。給定數字中的每一位都會向右移動給定的數量。到達數字末尾的任何位元都會被截斷（並且零出現在左側）。讓我們來看一個例子。

考慮 int result = 3 >> 2. 如您所知，3 的二進位是 011。讓我們來看看轉變的每次迭代。

初始

0	1	1

一班後

0	0	1

結果

0	0	0

二進位結果是000，十進位就是0。

不是(~)

寫~x。 not 運算子反轉給定數字的所有位元。我們將再次使用真值表來詳細說明。

考慮 int result = ~5。如您所知，5 的二進制數是 101。

Bit A	~ Bit A
1	0
0	1
1	0

因此，非運算的結果是010，即二進位的2。

左移和右移限制

這些輪班操作有一些值得注意的限制。對於初學者來說，您不能將位移位負數 - 這根本沒有意義！此外，移位超過分配給變數的位數將被視為未定義。你可以做到這一點，但它的輸出不能保證對於給定值是恆定的。最後，雖然不是一個限制，但移位 0 次根本不會執行移位。

輪到你了！

1. 完成以下每一項的真值表。考慮所有值都是無符號的。完成後轉換為十進制。
2. 8 & 2
3. 6 | 3
4. 7 ^ 5
5. (5 & 2) & (4 & 3)
6. (5 | 2) & (4 & 3)

7. (5 & 2) ^ (4 | 3)

8. 完成每項操作。考慮所有值都是無符號的，並且只要問題中的最長值需要是無符號的（即，如果最大值為 8，則處理 4 位元）。完成後轉換為十進制。

9. ~6

10. 9

11. ~(7 & 8)

12. (2 | 6) >> 1

13. 8>> (~2)

14. ~((3 >> 2) ^ ~7) & (~(7 >> 4) | 2)

回應樣本

問題1

• 8 & 2 → 1000 & 0010

Bit A	Bit B	AND
1	0	0
0	0	0
0	1	0
0	0	0

⇒ 0000，即十進位的 0。

• 6 | 3 → 110 | 011

Bit A	Bit B	OR
1	0	1
1	1	1
0	1	1

⇒ 111，十進位為 7。

• 7^5→111^101

Bit A	Bit B	XOR
1	1	0
1	0	1
1	1	0

⇒ 010，十進位 2。

• (5 & 2) & (4 & 3) → (101 & 010) & (100 & 011)

Bit A	Bit B	A AND B	Bit C	Bit D	C AND D	(A AND B) AND (C AND D)
1	0	0	1	0	0	0
0	1	0	0	1	0	0
1	0	0	0	1	0	0

⇒ 000，即十進位的 0。

• (5 | 2) & (4 & 3) → (101 | 010) & (100 & 011)

Bit A	Bit B	A OR B	Bit C	Bit D	C AND D	(A OR B) AND (C AND D)
1	0	1	1	0	0	0
0	1	1	0	1	0	0
1	0	1	0	1	0	0

⇒ 000，即十進位的 0。

• (5 & 2) ^ (4 | 3) → (101 & 010) ^ (100 | 011)

Bit A	Bit B	A AND B	Bit C	Bit D	C OR D	(A AND B) XOR (C OR D)
1	0	0	1	0	1	1
0	1	0	0	1	1	1
1	0	0	0	1	1	1

⇒ 111, which is 7 in decimal.

Question 2

• ~6 → ~110 ⇒ 011, which is 3 in decimal.

• 9 882c1bd3602a338c72ccc257e908feba> 1 → (010 | 110) >> 1 → 110 >> 1 ⇒ 011, which is 3 in decimal.

• 8 >> (~2) → 1000 >> ~(10) → 1000 >> (01) → 1000 >> 1 ⇒ 0100, which is 4 in decimal.

• ~((3 >> 2) ^ ~7) & (~(7 >> 4) | 2)

To solve this, I suggest splitting into halves:

~((3 >> 2) ^ ~7) and (~(7 >> 4) | 2)

~((3 >> 2) ^ ~7) → ~((011 >> 2) ^ ~(111)) → ~((000) ^ ~(111)) → ~(000 ^ 000) → 111
(~(7 >> 4) | 2) → (~(111 >> 4) | 010) → (~(000) | 010) → (111 | 010) → 111

Hence, 111 & 111 ⇒ 111, which is 7 in decimal.

Chapter 3: Applying Bitwise Operations in C

This chapter is all about writing C code that utilizes bitwise operators. Before we get to doing bitwise operations, we should begin by writing a function that can write the binary equivalent of a given variable.

To do this, we use a mask. We initialize it to contain a 1 in the most significant (leftmost in little-endian systems) bit followed by zeros. With each iteration of a loop, we right shift the mask by 1, moving the 1 all the way "across" the mask. When we use the & operator on the pointer and the mask, any non-zero value means that a 1 occurred somewhere in the result. Since there's only one 1 in the mask, we know exactly where this occurred. Since the loop moves from left to right, we can just append the corresponding bit's character to the string. The string is one character longer than the size because it needs to contain the null character (\0). This is how printf knows to stop printing, and omitting it can lead to numerous errors and/or unexpected behaviors (like the printing of other data from in memory).

void printBinary(unsigned int decimal) {

    // To determine size (in bits), we multiply the maximum size of an unsigned int by 8 (to convert from bytes to bits).
    int size = sizeof(decimal) * 8;

    // This counts the leading zeros of the number, then subtracts them from the size.
    // Hence, we start at the first bit set to 1 (unless decimal == 0)
    size -= __builtin_clz(decimal);

    if(size == 0) size = 1; // Handle zero case, we need one space to display "0."

    int curr = 0;
    char binary[size + 1];
    for(unsigned int mask = 1 e360cd6bcd3c1b37977442911f0d6d09>= 1) {
        if((decimal & mask) != 0) {
            binary[curr] = '1';
        } else {
            binary[curr] = '0';
        }
        curr++;
    }

    binary[curr] = '\0';

    printf("%s", binary);

}

Bitwise Assignment Operators

All bitwise operators, except for not (~), can be used in the assignment fashion. This means you can add an equals sign right next to one of the bitwise operator. For example, in

int a = 2;
a &= 7;

a is both the first operand and the destination. In other words, the value of a & 7 is stored in a. This works for all bitwise operators aside from the not (~) operator.

Now, I'd like to provide a few case study like prompts for you to try. Sample responses are available.

Case Study 1: Unix File Permissions

One use case of bitwise operations is in the Unix permission system. You've probably run the command

chmod 777 some-file

But what do each of the numbers mean? And why 7? The reality is, binary is at play here, and 7 should tip you off. Recall that 7 in binary is 111. The number being passed here is acting as three flags or booleans glued together.

The three digits specified are for three classes of users:

• The file owner;
• Group members of the file owner;
• and everyone else.

As I mentioned above, each digit is a conglomeration of three flags, each representing a permission. The flag (binary bit) in the fours place represents read permission, the twos place is for write permission, and the ones is for execute. So,

chmod 777 some-file

is doing this under the hood:

File Permissions: some-file

Group	Read	Write	Execute	Decimal
Owner	1	1	1	7
Owner's Group	1	1	1	7
Everyone Else	1	1	1	7

換句話說，所有的權限都是給所有人的。

任務

設計一個簡單的權限檢查器，它接受完整的檔案權限值（一個三位數）並檢查一組給定的特定權限（即擁有者寫入、每個人執行等）。例如，請查看第 3 章資料夾。

暗示

取得完整數字後，您需要將其轉換為 int（從 char*）。然後，使用模運算來分解每個權限集。請記住，第一個數字代表所有者的權限，第二個數字代表所有者的使用者群組，第三個數字代表所有人。

檢查特定權限是否出現在權限集中，按位以及給定的權限與集合。

案例 2：對網路進行子網路劃分

如果您曾經設定過路由器，您可能已經注意到配置「子網路遮罩」的選項。通常，該值設定為 255.255.255.0，但為什麼呢？首先，我們需要記住 IPv4 位址的每個位元組都以「.」分隔。當處理您最熟悉的網路類型（C 類網路）時，有 3 個位元組專用於網絡，最後一個位元組用於主機。

由於子網路遮罩只是一個掩碼，您可能會明白它的用途。對於從主機位元組「借用」的每一位，都會建立兩個子網路。

網路位址

網路位址將所有主機位元設定為0。這意味著任何位都被放棄以創建
子網路仍然可以設定為 1。

閱讀更多！

透過查看此網站以了解更多有關子網路的資訊。

任務

用 C 語言編寫一個程序，接收 IPv4 位址和子網路掩碼，尋找並輸出 IPv4 位址所在的網路位址。有關範例，請查看第 3 章資料夾。

暗示

您需要將位址和遮罩的每個位元組儲存為數值。若要尋找網路位址，請考慮遮罩和位址之間的哪種（位元）運算將產生預期的效果。

閉幕式

希望這個解釋對您有用！我寫它是因為我想自己學習位元運算。我已經檢查過了，但有些事情可能是錯誤的，所以請隨時透過拉取請求糾正我，甚至添加評論！另外，如果您有任何疑問，請發表評論！我等不及要跟你聊天了！最後，我很高興能為您提供此資源！

關於我

嗨！我是傑克遜，拉斐特學院電腦科學和法語專業的學生，也是一名有抱負的電腦科學研究員和教授。我目前對生物資訊學和低階程式設計/系統領域感興趣。要了解更多關於我的信息，請查看我的網站。

以上是位元運算概述的詳細內容。更多資訊請關注PHP中文網其他相關文章！