Gambaran Keseluruhan Operasi Bitwise

Siaran berikut diambil daripada repositori yang saya buat untuk membantu mempelajari (dan mengajar) tentang operasi bitwise. Anda boleh menemui repo itu di sini dan saya cadangkan menyemaknya—terdapat beberapa contoh kod dan penyelesaian di sana.

pengenalan

Matlamat repositori ini adalah untuk membiasakan anda dengan operasi bitwise, menerangkan maksudnya, cara ia berfungsi dan untuk kegunaannya.

Bab 1: Semuanya Binari

Dalam C (dan kebanyakan bahasa peringkat tinggi), pembolehubah kami mempunyai jenis. Jenis ini menunjukkan beberapa perkara. Sudah tentu, pembolehubah jenis int akan menyimpan nilai integer, tetapi kunci untuk memahami operasi bitwise ini adalah untuk mengetahui bahawa di bawah tudung, semua jenis disimpan dalam ingatan (di mana-mana, tindanan, timbunan, di mana sahaja) sebagai binari. Berikut ialah contoh perkara yang berlaku apabila anda menyimpan nilai integer mudah pada tindanan dalam C:

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

Selepas menyusun ke perhimpunan, kod mungkin kelihatan seperti ini (saya menggunakan pemasangan ARM di sini dan saya telah membuat anotasi kod menggunakan ulasan):

.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

Perhatikan bahawa kebanyakan penyusun akan tidak sebenarnya menyimpan pembolehubah seperti yang saya tunjukkan pada tindanan, kerana ia tidak digunakan. Walau bagaimanapun, jika ia digunakan beberapa kali, ia akan disimpan pada tindanan sesuatu seperti di atas.

Jika kita melihat lokasi di mana pembolehubah kita disimpan pada timbunan (semasa ia ada, sudah tentu), kita akan melihat sesuatu seperti:

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

Ini mengandaikan bahawa sistem anda adalah little-endian. Saya tidak akan pergi ke endianness di sini, tetapi anda boleh membaca lebih lanjut mengenainya di sini.

Perkara utama yang saya ingin anda perhatikan tentang jadual di atas ialah walaupun integer kita hanya 2 bit panjang, ia memerlukan 4 bait (32 bit) memori. Sekarang, jangan gentar—ini adalah perkara biasa dan dijangka. Salah satu daripada banyak perkara yang C dan pengkompil anda lakukan ialah menetapkan piawaian untuk jenis yang anda gunakan. Jadi apabila saya mencipta pembolehubah int, pengkompil tahu untuk memperuntukkan 4 bait (sekali lagi, 32 bit) memori. Kita juga boleh menguji ini menggunakan operator sizeof() dalam C.

The sizeof() Operator

sizeof() bukan fungsi C sebenar. Sebaliknya, pada masa penyusunan, pengkompil menggantikan ungkapan dengan saiz jenis data yang diberikan. Anda juga boleh menggunakan ini dengan jenis anda sendiri, seperti typedefs dan/atau struct:

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

Satu perkara lain yang mungkin anda tanyakan ialah cara nombor negatif disimpan. Soalan yang sangat baik. Nombor boleh ditandatangani atau tidak ditandatangani, tetapi secara lalai, nombor itu ditandatangani. Jika integer ditandatangani, ia mengorbankan bit yang paling penting untuk menjadi "bit tanda." Jika bit tanda ialah 1, nombornya adalah negatif; jika tidak ia positif. Pembaca yang bijak mungkin menyedari bahawa perubahan yang berlaku di sini adalah dalam julat nombor yang mungkin. Pertimbangkan nombor 8-bit. Terdapat 256 nombor yang mungkin untuk diwakili (diberikan oleh 2^8). Dengan integer 8-bit yang tidak ditandatangani, nilai 0–255 boleh diwakili; dengan int 8-bit yang ditandatangani, -128–127 boleh diwakili.

Untuk mendapatkan songsangan nombor binari, gunakan pujian dua. Mari cari -5 dalam binari.

1. Mulakan dengan 5. Dalam binari, 5 ialah 0101. 0 di hadapan ialah tanda.
2. Terbalikkan setiap bit. 0101 → 1010.
3. Tambah 1 pada nombor ini (abaikan sebarang kemungkinan limpahan). 1010 + 0001 = 1011.

Giliran Anda!

1. Sahkan bahawa -5 ialah 1011 dalam binari dengan melakukan dua pujian padanya untuk mendapatkan 5, atau 0101.
2. Tulis atur cara C yang mencetak saiz int dalam kedua-dua bait dan bit. Gunakan kod di atas sebagai titik permulaan. Petunjuk: untuk menukar daripada bait kepada bit, berapa banyak bit dalam bait?
3. Isi jadual berikut dengan saiz jenis yang berbeza, ubah suai atur cara anda untuk menyemaknya.

Type	Size (bytes)	Size (bits)
int
int64_t
int8_t
char
bool (you'll need to #include )
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 <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

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

Hasil operasi xor ialah 110, yang apabila ditukar kepada perpuluhan ialah 6.

Shift Kiri (<<)

Ditulis x << jumlah Tidak seperti operator di atas, operator ini hanya beroperasi pada satu nombor. Setiap bit dalam nombor yang diberikan dialihkan ke kiri dengan jumlah yang diberikan. Mana-mana bit yang mencapai penghujung nombor dipotong (dan sifar muncul di sebelah kanan). Mari kita lihat contoh.

Pertimbangkan hasil int = 5 << 2. Seperti yang anda tahu, 5 ialah 101 dalam binari. Mari kita lihat setiap lelaran peralihan.

Awal

1	0	1

Selepas satu syif

0	1	0

Keputusan

1	0	0

Hasil binari ialah 100, iaitu 4 dalam perpuluhan.

Shift Kanan (>>)

Ditulis x >> jumlah Operator ini sama seperti anjakan kiri, kecuali ia berfungsi dalam arah yang bertentangan. Setiap bit dalam nombor yang diberikan dianjakkan ke kanan dengan jumlah yang diberikan. Mana-mana bit yang mencapai penghujung nombor dipotong (dan sifar muncul di sebelah kiri). Mari kita lihat contoh.

Pertimbangkan hasil int = 3 >> 2. Seperti yang anda tahu, 3 ialah 011 dalam binari. Mari kita lihat setiap lelaran peralihan.

Awal

0	1	1

Selepas satu syif

0	0	1

Keputusan

0	0	0

Hasil binari ialah 000, iaitu 0 dalam perpuluhan.

bukan (~)

Ditulis ~x. Operator bukan menyongsangkan semua bit nombor yang diberikan. Sekali lagi, kami akan menggunakan jadual kebenaran untuk menghuraikan.

Pertimbangkan hasil int = ~5. Seperti yang anda tahu, 5 ialah 101 dalam binari.

Bit A	~ Bit A
1	0
0	1
1	0

Oleh itu, hasil daripada operasi bukan ialah 010, iaitu 2 dalam binari.

Sekatan Shift Kiri & Shift Kanan

Terdapat beberapa sekatan ketara dikenakan pada operasi syif ini. Sebagai permulaan, anda tidak boleh mengalih bit beberapa kali negatif—itu tidak masuk akal! Selain itu, peralihan lebih daripada bilangan bit yang diperuntukkan kepada pembolehubah anda dianggap tidak ditentukan. Anda boleh melakukannya, tetapi outputnya tidak dijamin tetap untuk nilai tertentu. Akhir sekali, walaupun bukan sekatan setiap kata, peralihan 0 kali tidak menghasilkan peralihan.

Giliran Anda!

1. Lengkapkan jadual kebenaran untuk setiap yang berikut. Pertimbangkan semua nilai tidak ditandatangani. Tukar kepada perpuluhan apabila lengkap.
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. Lengkapkan setiap operasi. Pertimbangkan semua nilai untuk tidak ditandatangani dan selagi nilai terpanjang dalam masalah itu perlu (iaitu, jika anda mempunyai nilai terbesar 8, berurusan dengan 4 bit). Tukar kepada perpuluhan apabila lengkap.

9. ~6

10. 9 << 4 (di sini pertimbangkan nilai sebagai panjang 32, jadi ada ruang untuk beralih ke kiri).

11. ~(7 & 8)

12. (2 | 6) >> 1

13. 8 >> (~2)

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

Contoh Respons

Soalan 1

• 8 & 2 → 1000 & 0010

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

⇒ 0000, iaitu 0 dalam perpuluhan.

• 6 | 3 → 110 | 011

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

⇒ 111, iaitu 7 dalam perpuluhan.

• 7 ^ 5 → 111 ^ 101

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

⇒ 010, iaitu 2 dalam perpuluhan.

• (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, iaitu 0 dalam perpuluhan.

• (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, iaitu 0 dalam perpuluhan.

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

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

Dalam erti kata lain, semua kebenaran diberikan kepada semua.

Tugasan

Reka bentuk penyemak kebenaran ringkas yang mengambil nilai kebenaran fail penuh (nombor tiga digit) dan menyemak set kebenaran tertentu (iaitu, pemilik menulis, semua orang melaksanakan, dll.). Sebagai contoh, semak folder Bab 3.

Petunjuk

Selepas mengambil nombor penuh, anda perlu menukarnya kepada int (daripada aksara*). Kemudian, gunakan aritmetik modular untuk memecahkan setiap set kebenaran. Ingat, digit pertama mewakili kebenaran pemilik, yang kedua adalah untuk kumpulan pengguna pemilik dan yang ketiga adalah untuk semua orang.

Untuk menyemak sama ada kebenaran tertentu berlaku dalam set kebenaran, bitwise dan kebenaran yang diberikan dengan set itu.

Kes 2: Subnet Rangkaian

Jika anda pernah mengkonfigurasi penghala, anda mungkin melihat pilihan untuk mengkonfigurasi "subnet mask." Biasanya, ini ditetapkan kepada 255.255.255.0, tetapi mengapa? Pertama, kita perlu ingat bahawa setiap bait alamat IPv4 dipisahkan oleh '.'. Apabila berurusan dengan jenis rangkaian yang paling anda kenali (rangkaian kelas C), terdapat 3 bait khusus untuk rangkaian dan bait terakhir adalah untuk hos.

Memandangkan subnet mask ialah topeng, anda mungkin memahami tujuannya. Untuk setiap bit yang anda "pinjam" daripada bait hos, dua subnet dicipta.

Alamat Rangkaian

alamat rangkaian mempunyai semua hos bit ditetapkan kepada 0. Ini bermakna sebarang bit diserahkan untuk mencipta
subnet masih boleh ditetapkan kepada 1.

Baca Lagi!

Ketahui lebih lanjut tentang subnet dengan menyemak tapak web ini.

Tugasan

Dalam C, tulis program yang mengambil alamat IPv4 dan subnet mask dan cari serta keluarkan alamat rangkaian tempat alamat IPv4 itu tinggal. Sebagai contoh, semak folder Bab 3.

Petunjuk

Anda perlu menyimpan setiap bait alamat dan topeng sebagai nilai berangka. Untuk mencari alamat rangkaian, pertimbangkan operasi (bitwise) antara topeng dan alamat yang akan menghasilkan kesan yang dimaksudkan.

Penutup

Saya harap penerangan ini berguna untuk anda! Saya menulisnya kerana saya ingin belajar tentang operasi bitwise sendiri. Saya telah menyemaknya, tetapi beberapa perkara mungkin salah, jadi sila betulkan saya melalui permintaan tarik, atau tambahkan ulasan! Juga, jika anda mempunyai sebarang soalan, tinggalkan komen! Saya tidak sabar untuk berbual dengan anda! Untuk menutup, saya sangat gembira kerana dapat menyediakan sumber ini untuk anda!

Tentang Saya

Hai! Saya Jackson, pelajar sains komputer & Perancis di Kolej Lafayette dan seorang penyelidik serta profesor yang bercita-cita tinggi dalam sains komputer. Saya kini berminat dalam bidang bioinformatik dan pengaturcaraan/sistem peringkat rendah. Untuk mengetahui lebih lanjut tentang saya, lihat tapak saya.

Atas ialah kandungan terperinci Gambaran Keseluruhan Operasi Bitwise. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!