비트별 연산 개요-C++-php.cn

An Overview of Bitwise Operations

다음 게시물은 비트 연산에 대해 배우고 가르치기 위해 만든 저장소에서 가져온 것입니다. 여기에서 해당 저장소를 찾을 수 있으며 확인해 보시기 바랍니다. 거기에 몇 가지 코드 예제와 솔루션이 있습니다.

소개

이 저장소의 목표는 비트 연산을 익히고 비트 연산이 무엇인지, 어떻게 작동하는지, 어떤 용도로 사용할 수 있는지 설명하는 것입니다.

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

로그인 후 복사

대부분의 컴파일러는 내가 스택에 표시한 것과 같은 변수가 사용되지 않기 때문에 실제로 저장하지 않습니다. 하지만 여러 번 사용하게 되면 위와 같은 스택에 저장되게 됩니다.

스택에서 변수가 저장된 위치를 살펴보면(물론 변수가 있는 동안) 다음과 같은 내용을 볼 수 있습니다.

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을 표현할 수 있습니다.

2진수의 역수를 얻으려면 2의 칭찬을 사용하세요. 바이너리에서 -5를 찾아봅시다.

5로 시작하세요. 이진수로 5는 0101입니다. 맨 앞의 0은 부호입니다.
각 비트를 반전시킵니다. 0101 → 1010.
이 숫자에 1을 더합니다(오버플로 가능성은 무시). 1010 + 0001 = 1011.

당신 차례입니다!

-5에 대해 2의 칭찬을 수행하여 5, 즉 0101을 얻음으로써 이진수로 -5가 1011인지 확인합니다.
int의 크기를 바이트와 비트 모두로 인쇄하는 C 프로그램을 작성하세요. 위의 코드를 시작점으로 사용하세요. 힌트: 바이트를 비트로 변환하려면 바이트에 몇 비트가 있나요?
다음 표에 다양한 유형의 크기를 채우고 프로그램을 수정하여 확인하세요.

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

Start with -5: 1011.
Invert each bit: 1011 → 0100.
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

xor 연산의 결과는 110이고 이를 십진수로 환산하면 6입니다.

왼쪽 시프트(<<)

작성 x << 금액 위의 연산자와 달리 이 연산자는 하나의 숫자에만 작동합니다. 주어진 숫자의 각 비트는 주어진 양만큼 왼쪽으로 이동됩니다. 숫자 끝에 도달하는 모든 비트는 잘립니다(그리고 오른쪽에 0이 나타납니다). 예시를 살펴보겠습니다.

int result = 5 <<를 고려하세요. 2. 아시다시피 5는 이진수로 101입니다. 교대조의 각 반복을 살펴보겠습니다.

초기

1	0	1

1교대 후

0	1	0

결과

1	0	0

이진수 결과는 100이며 십진수는 4입니다.

오른쪽 Shift(>>)

작성x>> 금액 이 연산자는 반대 방향으로 작동한다는 점을 제외하면 왼쪽 시프트와 같습니다. 주어진 숫자의 각 비트는 주어진 양만큼 오른쪽으로 이동됩니다. 숫자 끝에 도달하는 모든 비트는 잘립니다(그리고 왼쪽에 0이 나타납니다). 예시를 살펴보겠습니다.

int 결과 = 3을 고려하세요. >> 2. 아시다시피 3은 이진수로 011입니다. 교대조의 각 반복을 살펴보겠습니다.

초기

0	1	1

1교대 후

0	0	1

결과

0	0	0

이진수 결과는 000이며, 십진수는 0입니다.

아니다(~)

작성 ~x. not 연산자는 주어진 숫자의 모든 비트를 반전시킵니다. 다시 한 번 진리표를 사용하여 자세히 설명하겠습니다.

int 결과 = ~5를 고려하세요. 아시다시피 5는 2진수로 101입니다.

Bit A	~ Bit A
1	0
0	1
1	0

따라서 not 연산의 결과는 010, 즉 이진수 2입니다.

왼쪽 Shift 및 오른쪽 Shift 제한

이러한 교대 근무에는 몇 가지 주목할만한 제한 사항이 있습니다. 우선, 비트를 음수로 이동할 수 없습니다. 이는 말이 되지 않습니다! 또한 변수에 할당된 비트 수 이상으로 이동하는 것은 정의되지 않은 것으로 간주됩니다. 할 수 있지만 출력이 주어진 값에 대해 일정하다는 보장은 없습니다. 마지막으로, 말마다 제한은 아니지만 0번 시프트하는 것은 단순히 시프트를 수행하지 않습니다.

당신 차례입니다!

다음 각 항목에 대한 진리표를 작성하세요. 모든 값은 부호가 없는 것으로 간주합니다. 완료되면 10진수로 변환하세요.
8&2
6 | 3
7^5
(5 & 2) & (4 & 3)
(5 | 2) & (4 & 3)
(5 & 2) ^(4 | 3)
각 작업을 완료하세요. 문제에서 가장 긴 값이 필요한 한 모든 값은 부호가 없는 것으로 간주합니다(즉, 가장 큰 값이 8인 경우 4비트를 처리합니다). 완료되면 10진수로 변환하세요.
~6
9 << 4(여기서는 길이가 32인 값을 고려하므로 왼쪽 시프트를 위한 공간이 있습니다).
~(7&8)
(2 | 6) >> 1
8>> (~2)
~((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	Bit C	Bit D
1	0	1	0
0	1	0	1
1	0	0	1

⇒ 000(십진수 0)

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

Bit A	Bit B	A OR B	Bit C	Bit D
1	0	1	1	0
0	1	1	0	1
1	0	1	0	1

⇒ 000(십진수 0)

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

Bit A	Bit B	Bit C	Bit D	C OR D	(A AND B) XOR (C OR D)
1	0	1	0	1	1
0	1	0	1	1	1
1	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

즉, 모든 권한이 모두에게 부여됩니다.

일

전체 파일 권한 값(3자리 숫자)을 받아 특정 특정 권한 세트(예: 소유자 쓰기, 모든 사람 실행 등)를 확인하는 간단한 권한 검사기를 설계하세요. 예시는 Chapter 3 폴더를 확인해보세요.

힌트

전체 숫자를 가져온 후에는 정수(문자*에서)로 변환해야 합니다. 그런 다음 모듈식 연산을 사용하여 각 권한 집합을 분류합니다. 첫 번째 숫자는 소유자의 권한을 나타내고, 두 번째 숫자는 소유자의 사용자 그룹, 세 번째 숫자는 모든 사람을 나타냅니다.

권한 집합에서 특정 권한이 발생하는지 확인하려면 비트 단위로 해당 집합으로 주어진 권한을 확인하세요.

사례 2: 네트워크 서브넷화

라우터를 구성한 적이 있다면 '서브넷 마스크' 구성 옵션을 발견했을 것입니다. 보통 255.255.255.0으로 설정되어 있는데 왜 그럴까요? 먼저, IPv4 주소의 각 바이트는 '.'으로 구분된다는 점을 기억해야 합니다. 가장 친숙한 네트워크 유형(클래스 C 네트워크)을 다룰 때 네트워크 전용 3바이트가 있고 마지막 바이트는 호스트용입니다.

서브넷 마스크는 마스크이므로 그 용도를 파악하고 계실 수도 있습니다. 호스트 바이트에서 "빌려온" 각 비트에 대해 두 개의 서브넷이 생성됩니다.

네트워크 주소

네트워크 주소에는 모든 호스트 비트가 0으로 설정되어 있습니다. 이는 모든 비트가 생성을 위해 항복되었음을 의미합니다
서브넷은 여전히 1로 설정될 수 있습니다.

자세히 읽어보세요!

이 웹사이트를 확인하여 서브넷에 대해 자세히 알아보세요.

일

C에서 IPv4 주소와 서브넷 마스크를 입력받아 IPv4 주소가 상주하는 네트워크 주소를 찾아서 출력하는 프로그램을 작성하세요. 예를 들어 Chapter 3 폴더를 확인하세요.

힌트

주소와 마스크의 각 바이트를 숫자 값으로 저장해야 합니다. 네트워크 주소를 찾으려면 마스크와 주소 중 어떤 (비트별) 연산이 의도한 효과를 생성하는지 고려하세요.

폐쇄

이 설명이 여러분에게 도움이 되었기를 바랍니다! 비트 연산을 직접 배우고 싶어서 썼습니다. 확인했지만 잘못된 부분이 있을 수 있으니 언제든지 풀 리퀘스트를 통해 수정하거나 댓글을 추가해 주세요! 또한, 궁금한 점이 있으시면 댓글을 남겨주세요! 나는 당신과 채팅하고 싶어요! 마지막으로, 여러분에게 이 리소스를 제공할 수 있어서 정말 기쁩니다!

나에 대해

안녕하세요! 저는 Lafayette College에서 컴퓨터 과학 및 프랑스어를 전공하는 학생이자 야심찬 연구원이자 컴퓨터 과학 교수인 Jackson입니다. 저는 현재 생물정보학 및 저수준 프로그래밍/시스템 분야에 관심이 있습니다. 나에 대해 더 자세히 알아보려면 내 사이트를 확인하세요.

위 내용은 비트별 연산 개요의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!