An Overview of Bitwise Operations

The following post was taken from a repository I created to help learn (and teach) about bitwise operations. You can find that repo here, and I'd suggest checking it out—there's some code examples and solutions there.

Introduction

The goal of this repository is to acquaint you with bitwise operations, explaining what they are, how they work, and what they can be used for.

Chapter 1: It's All Binary

In C (and most high-level languages), our variables havetypes. These types are indicative of a few things. Of course, a variable of type int will store an integer value, but the key to understanding these bitwise operations is to know that under the hood, all types are stored in memory (anywhere, stack, heap, wherever) as binary. Here's an example of what happens when you store a simple integer value on the stack in C:

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

After compiling to assembly, the code might look like this (I'm using ARM assembly here, and I've annotated the code using comments):

.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

Note that most compilers wouldnotactually store a variable like the one I showed on the stack, as it is unused. However, if it is used multiple times, it would be stored on the stack something like the above.

If we looked at the location where our variable was stored on the stack (while it is there, of course), we would see something like:

This assumes that your system is little-endian. I won't go into endianness here, but you can read more about it here.

The key thing I'd like you to notice about the table above is that even though our integer is only 2 bits long, it takes up 4 bytes (32 bits) of memory. Now, don't freak out—this is normal and expected. One of the many things that C and your compiler do is set standards for the types you invoke. So when I create an int variable, the compiler knows to allocate 4 bytes (again, 32 bits) of memory. We can even test this using the sizeof() operator in C.

The sizeof() Operator

sizeof() is not an actual C function. Instead, at compile time, the compiler replaces the expression with the size of the given data type. You can even use this with your own types, like typedefs and/or structs:

#include  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; }

Copy after login

One other thing you might be asking is how negative numbers are stored. Excellent question. Numbers can besignedorunsigned, but by default, they're signed. If an integer is signed, it sacrifices its most significant bit to be the "sign bit." If the sign bit is 1, the number is negative; otherwise it's positive. An astute reader might realize that the change that happens here is in the range of possible numbers. Consider 8-bit numbers. There are 256 possible numbers to represent (given by 2^8). With an unsigned 8-bit integer, the values 0–255 can be represented; with a signed 8-bit int, -128–127 can be represented.

To get the inverse of a binary number, use two's compliment. Let's find -5 in binary.

1. Start with 5. In binary, 5 is 0101. The leading 0 is the sign.
2. Invert each bit. 0101 → 1010.
3. Add 1 to this number (ignoring any possible overflow). 1010 + 0001 = 1011.

Your Turn!

1. Confirm that -5 is 1011 in binary by performing two's compliment on it to get 5, or 0101.
2. Write a C program that prints the size of an int in both bytes and bits. Use the code above as a starting point.Hint: to convert from bytes to bits, how many bits are in a byte?
3. Fill in the following table with sizes of different types, modifying your program to check them.

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  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

TakeThisHome

The main point I'd like you to keep in mind is thatwith 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, abitwise operationis 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 donotreturn 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 1if 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 1if 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になります。

左シフト (<<)

×と書かれています<< amount 上記の演算子とは異なり、この演算子は 1 つの数値のみを操作します。指定された数値の各ビットが指定された量だけ左にシフトされます。数値の末尾に達するビットは切り捨てられます (右側にゼロが表示されます)。例を見てみましょう。

int result = 5 << を考えてみましょう。 2. ご存知のとおり、5 は 2 進数で 101 です。シフトの各反復を見てみましょう。

イニシャル

1シフト後

結果

2 進数の結果は 100 となり、10 進数では 4 になります。

右シフト (>>)

×と書きました>> amount この演算子は、逆方向に動作することを除けば、左シフトとまったく同じです。指定された数値の各ビットは、指定された量だけ右にシフトされます。数値の末尾に達するビットは切り捨てられます (左側にゼロが表示されます)。例を見てみましょう。

int result = 3 を考慮します>> 2. ご存知のとおり、3 は 2 進数の 011 です。シフトの各反復を見てみましょう。

イニシャル

1シフト後

結果

バイナリの結果は 000 で、これは 10 進数の 0 です。

違います (~)

~xと書きました。 not 演算子は、指定された数値のすべてのビットを反転します。もう一度、真理値表を使用して詳しく説明します。

int result = ~5 を考えてみましょう。ご存知のとおり、5 は 2 進数で 101 です。

したがって、not 演算の結果は 010、つまり 2 進数の 2 になります。

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

これらのシフト業務にはいくつかの注目すべき制限が課されています。まず、ビットを負の回数だけシフトすることはできません。これでは意味がありません。また、変数に割り当てられたビット数を超えてシフトすると、未定義とみなされます。それを行うことはできますが、その出力が指定された値に対して一定であるとは保証されません。最後に、厳密に言えば制限ではありませんが、0 回シフトしてもシフトは実行されません。

あなたの番！

1. 以下のそれぞれについて真理値表を完成させてください。すべての値は符号なしであると考えてください。完了したら 10 進数に変換します。
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 ビットを処理します) であると考えてください。完了したら 10 進数に変換します。

9. ~6

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

~(7 & 8)
(2 | 6) >> 1
8 >> (~2)
~((3 >> 2) ^ ~7) & (~(7 >> 4) | 2)
応答例

質問1

⇒ 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;

Copy after login

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 つのサブネットが作成されます。

ネットワークアドレス

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

続きを読む！

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

The above is the detailed content of An Overview of Bitwise Operations. For more information, please follow other related articles on the PHP Chinese website!