ビット単位の演算の概要

次の投稿は、ビット単位の演算について学習 (および教育) するために私が作成したリポジトリから抜粋したものです。そのリポジトリはここにあります。チェックしてみることをお勧めします。そこにはコード例と解決策がいくつかあります。

導入

このリポジトリの目的は、ビット単位の操作について説明し、ビット単位の操作とは何か、どのように機能するのか、何に使用できるのかを説明することです。

第 1 章: すべてはバイナリです

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

ほとんどのコンパイラは、私が示したような変数は未使用であるため、実際にはスタックに保存しないことに注意してください。ただし、複数回使用される場合は、上記のようにスタックに保存されます。

変数がスタック上に保存されている場所を確認すると (もちろん、変数がそこにある間)、次のようになります。

これは、システムがリトルエンディアンであることを前提としています。ここではエンディアンについては触れませんが、詳細についてはここで読むことができます。

上の表で注目していただきたい重要な点は、整数の長さがわずか 2 ビットであるにもかかわらず、4 バイト (32 ビット) のメモリを使用するということです。心配しないでください。これは正常であり、予想されることです。 C とコンパイラが行う多くのことの 1 つは、呼び出す型の標準を設定することです。したがって、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 つ気になるのは、負の数値がどのように保存されるかということです。素晴らしい質問です。数値は署名または符号なしにすることができますが、デフォルトでは署名されています。整数が符号付きの場合、その最上位ビットが犠牲になって「符号ビット」になります。符号ビットが 1 の場合、数値は負になります。それ以外の場合はポジティブです。賢明な読者なら、ここで起こる変化は考えられる数値の範囲内であることに気づくかもしれません。 8 ビット数値を考えてみましょう。表現できる数値は 256 個あります (2^8 で与えられます)。符号なし 8 ビット整数では、0 ～ 255 の値を表すことができます。符号付き 8 ビット int を使用すると、-128 ～ 127 を表現できます。

2 進数の逆数を取得するには、2 の補数を使用します。 2 進数で -5 を見つけてみましょう。

1. 5 から始めます。2 進数では、5 は 0101 です。先頭の 0 は符号です。
2. 各ビットを反転します。 0101 → 1010.
3. この数値に 1 を加えます (オーバーフローの可能性は無視します)。 1010 + 0001 = 1011.

あなたの番です！

1. -5 を 2 の補数で 5、つまり 0101 にすることで、-5 が 2 進数の 1011 であることを確認します。
2. int のサイズをバイトとビットの両方で出力する C プログラムを作成します。上記のコードを開始点として使用してください。 ヒント: バイトからビットに変換するには、1 バイトには何ビットが含まれますか?
3. 次の表にさまざまなタイプのサイズを入力し、プログラムを変更して確認してください。

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 <stdio.h>

 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

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:

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:

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:

XOR 演算の結果は 110 で、10 進数に変換すると 6 になります。

左シフト (<<)

×と書かれています<

イニシャル

1 シフト後

結果

イニシャル

1 シフト後

結果

左シフトと右シフトの制限

これらのシフト操作には、いくつかの注目すべき制限が課されています。まず、ビットを負の回数だけシフトすることはできません。これでは意味がありません。また、変数に割り当てられたビット数を超えてシフトすると、未定義とみなされます。それはできます

が、その出力が指定された値に対して一定であるとは保証されません。最後に、厳密な制限ではありませんが、0 回シフトしてもシフトは実行されません。

以下のそれぞれについて真理値表を完成させてください。すべての値は符号なしであると考えてください。完了したら 10 進数に変換します。
8 & 2
6 | 3
7 ^ 5
(5 & 2) & (4 & 3)
(5 | 2) & (4 & 3)

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

8. 各操作を完了します。すべての値は符号なしであり、問​​題内の最長値が必要である限り (つまり、最大値が 8 の場合は 4 ビットを処理します) であると考えてください。完了したら 10 進数に変換します。

9. ~6

10. 9 << 4 (ここでは値の長さが 32 であると考えているため、左にシフトする余地があります)。

11. ~(7 & 8)

12. (2 | 6) >> 1

13. 8 >> (~2)

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

8 & 2 → 1000 & 0010

⇒ 0000、つまり 10 進数の 0。

• 6 | 3 → 110 | 011

⇒ 111、つまり 10 進数の 7。

• 7 ^ 5 → 111 ^ 101

⇒ 010、つまり 10 進数の 2。

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

⇒ 000、つまり 10 進数の 0。

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

⇒ 000、つまり 10 進数の 0。

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

⇒ 111, which is 7 in decimal.

Question 2

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

• 9 << 4 → 001001 << 4 ⇒ 100100, which is 36 in decimal.

• ~(7 & 8) → ~(0111 & 1000) → ~(0000) ⇒ 1111, which is 15 in decimal.

• (2 | 6) >> 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 << (size - 1); mask != 0; mask >>= 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

言い換えると、すべての権限が全員に与えられます。

タスク

完全なファイル権限値 (3 桁の数字) を取得し、特定の権限セット (所有者による書き込み、全員の実行など) をチェックする単純な権限チェッカーを設計します。例として、第 3 章のフォルダーを確認してください。

ヒント

完全な数値を取得した後、それを (char* から) int に変換する必要があります。次に、モジュラー算術を使用して、各権限セットを細分化します。最初の数字は所有者の権限を表し、2 番目の数字は所有者のユーザー グループに対するもの、3 番目の数字は全員に対するものであることに注意してください。

特定のアクセス許可がアクセス許可セット内で発生するかどうかをビット単位で確認し、指定されたアクセス許可をセットで確認します。

ケース 2: ネットワークのサブネット化

ルーターを設定したことがある方は、「サブネット マスク」を設定するオプションに気づいたかもしれません。通常、これは 255.255.255.0 に設定されますが、なぜですか?まず、IPv4 アドレスの各バイトは「.」で区切られていることを覚えておく必要があります。あなたが最もよく知っているネットワークのタイプ (クラス C ネットワーク) を扱う場合、ネットワーク専用の 3 バイトがあり、最後のバイトはホスト用です。

サブネット マスクはマスクなので、その目的を理解しているかもしれません。ホスト バイトから「借用」したビットごとに、2 つのサブネットが作成されます。

ネットワークアドレス

ネットワーク アドレス のすべての ホスト ビットが 0 に設定されています。これは、作成するために任意のビットが放棄されたことを意味します
サブネットは引き続き 1 に設定できます。

続きを読む！

サブネットについて詳しくは、この Web サイトをご覧ください。

タスク

C で、IPv4 アドレスとサブネット マスクを受け取り、IPv4 アドレスが存在するネットワーク アドレスを検索して出力するプログラムを作成します。例については、第 3 章のフォルダーを確認してください。

ヒント

アドレスとマスクの各バイトを数値として保存する必要があります。ネットワーク アドレスを見つけるには、マスクとアドレスの間のどの (ビットごとの) 演算が意図した効果を生み出すかを検討してください。

終わりに

この説明がお役に立てば幸いです!ビット演算について自分でも学びたかったので書きました。確認しましたが、間違っている点もあるかもしれないので、プルリクエストで修正したり、コメントを追加したりしてください。また、ご質問がございましたら、コメントを残してください。あなたとチャットするのが待ちきれません!最後になりますが、このリソースを提供できたことをとても嬉しく思います!

私について

こんにちは！私はジャクソンです。ラファイエット大学でコンピューター サイエンスとフランス語を学ぶ学生で、コンピューター サイエンスの研究者兼教授を目指しています。私は現在、バイオインフォマティクスと低レベルプログラミング/システムの分野に興味を持っています。私について詳しく知りたい場合は、私のサイトをチェックしてください。

以上がビット単位の演算の概要の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。