먼저 about 비트를 기억하고 비트 연산자가 짧습니다.
비트 이진수입니다. 컴퓨터가 이해할 수 있는 가장 작은 데이터 단위입니다. In은 0(OFF를 나타냄) 및 1(ON을 나타냄) 두 값 중 하나만 가질 수 있습니다. .
비트 연산자 프로그램에서 비트 수준으로 작동하는 연산자입니다.
이 연산자는 프로그램의 비트를 조작하는 데 사용됩니다.
C에는 6개의 비트 연산자가 있습니다 -
-
비트 AND(&)
-
비트 OR(OR)
-
비트 XOR(XOR)
-
비트 왼쪽 시프트(<<)/p>
-
비트 오른쪽 시프트(>>)
-
비트 단위 아님(~)
https://www.tutorialspoint.com/cprogramming/c_bitwise_operators.htm
이제 비트로 작업할 때 도움이 될 수 있는 몇 가지 중요한 전술에 대해 알아보겠습니다.
두 숫자 바꾸기(비트 XOR 사용)
비트 XOR 연산자를 사용하여 두 값을 교환할 수 있습니다. 구현은 -
예시
#include <stdio.h>
int main(){
int x = 41;
int y = 90;
printf("Values before swapping! \n");
printf("x = %d \t", x);
printf("y = %d \n", y);
x = x ^ y;
y = y ^ x;
x = x ^ y;
printf("Values after swapping! \n");
printf("x = %d \t", x);
printf("y = %d \n", y);
return 0;
} 출력
Values before swapping! x = 41 y = 90 Values before swapping! x = 90 y = 41
MSB(최상위 비트)를 찾는 효율적인 방법
모든 정수 값에 대해 최상위 비트가 효과적인 방법임을 알 수 있습니다. 이것은 비트 시프트 연산자와 함께 또는 연산자를 사용하여 수행됩니다. 이 방법은 o(1) 시간 복잡도에서 MSB를 찾을 수 있습니다.
정수의 크기는 프로그램을 생성하기 위해 미리 정의되어야 합니다.
예시
32비트 정수의 MSB를 찾는 프로그램 -
#include <stdio.h>
int findMSB(int x){
x |= x>>1;
x |= x>>2;
x |= x>>4;
x |= x>>8;
x |= x>>16;
x = x+1;
return(x >> 1);
}
int main(){
int x = 49;
printf("The number is %d\n", x);
int msb = findMSB(x);
printf("MSB of the number is %d\n", msb);
} 출력
The number is 49 MSB of the number is 32
1부터 n까지의 모든 숫자의 XOR을 직접 계산합니다.
0에서 n까지의 XOR을 주의 깊게 관찰하면 일반적인 패턴을 도출할 수 있습니다. 여기에 설명되어 있습니다 -
예시
#include <stdio.h>
// Direct XOR of all numbers from 1 to n
int findXORuptoN(int n){
switch( n%4){
case 0: return n;
case 1: return 1;
break;
case 2: return n+1;
break;
case 3: return 0;
break;
default: break;
}
}
int main(){
int n = 9870;
int xorupton = findXORuptoN(n);
printf("XOR of all number up to %d is %d\n", n, xorupton);
} 출력
XOR of all number up to 9870 is 9871
합과 XOR이 같은 수와 작거나 같은 수의 조합의 총 수를 직접 계산합니다.
비트 시프팅 연산자를 사용하면 작업을 쉽게 수행할 수 있고 시간이 덜 소요됩니다.
예시
#include <stdio.h>
int countValues(int n){
int unset=0;
while (n){
if ((n & 1) == 0)
unset++;
n=n>>1;
}
return (1<<unset);
}
int main(){
int n = 32;
printf("%d", countValues(n));
} 출력
32
정수에서 앞뒤 0의 개수 찾기
비트 조작 덕분에 정수의 선행 및 후행 0의 수를 찾는 내장된 메서드가 있습니다.
* GCC 내장 기능입니다.
예시
#include <stdio.h>
int main(){
int n = 32;
printf("The integer value is %d\n", n);
printf("Number of leading zeros is %d\n", __builtin_clz(n));
printf("Number of trailing zeros is %d\n",__builtin_clz(n));
} 출력
The integer value is 32 Number of leading zeros is 26 Number of trailing zeros is 26
숫자가 2의 거듭제곱인지 확인하시겠습니까?
숫자가 2의 거듭제곱인지 확인하려면 비트 연산자를 사용하면 쉽게 확인할 수 있습니다.
예시
#include <stdio.h>
int isPowerof2(int n){
return n && (!(n&(n-1)));
}
int main(){
int n = 22;
if(isPowerof2(n))
printf("%d is a power of 2", n);
else
printf("%d is not a power of 2", n);
} 출력
22 is not a power of 2
집합의 모든 부분집합의 XOR 찾기
이것은 2개 이상의 요소가 있는 경우 모든 하위 집합의 XOR이 항상 0이고 그렇지 않은 경우 숫자라는 사실을 사용하여 수행할 수 있습니다.
예시
#include <stdio.h>
int findsubsetXOR (int set[], int size){
if (size == 1){
return set[size - 1];
}
else
return 0;
}
int main (){
int set[] = { 45, 12 };
int size = sizeof (set) / sizeof (set[0]);
printf ("The XOR of all subsets of set of size %d is %d\n", size,
findsubsetXOR (set, size));
int set2[] = { 65 };
size = sizeof (set2) / sizeof (set2[0]);
printf ("The XOR of all subsets of set of size %d is %d\n", size,
findsubsetXOR (set2, size));
} 출력
The XOR of all subsets of set of size 2 is 0 The XOR of all subsets of set of size 1 is 65
주어진 이진수 정수를 변환하려면
자동 C의 키워드는 작업을 수행하는 데 사용됩니다.
예시
#include <stdio.h>
int main (){
auto integer = 0b0110110;
printf("The integer conversion of binary number '0110110' is %d", integer);
} 출력
The integer conversion of binary number '0110110' is 54
숫자의 모든 비트 뒤집기
모든 비트가 설정된 숫자에서 숫자를 빼서 숫자의 모든 비트를 뒤집을 수 있습니다.
Number = 0110100 The number will all bits set = 1111111 Subtraction -> 1111111 - 0110100 = 1001011 (number with flipped bits)
예시
#include <stdio.h>
int main (){
int number = 23;
int n = number;
n |= n>>1;
n |= n>>2;
n |= n>>4;
n |= n>>8;
n |= n>>16;
printf("The number is %d\n", number);
printf("Number with reversed bits %d\n", n-number);
} 출력
The number is 23 Number with reversed bits 8
비트에 대체 패턴이 있는지 확인
비트별 XOR 연산을 사용하여 숫자의 비트가 대체 패턴인지 여부를 찾을 수 있습니다. 아래 코드는 다음을 수행하는 방법을 보여줍니다 -
예시
#include <stdio.h>
int checkbitpattern(int n){
int result = n^(n>>1);
if(((n+1)&n) == 0)
return 1;
else
return 0;
}
int main (){
int number = 4;
if(checkbitpattern == 1){
printf("Bits of %d are in alternate pattern", number);
}
else
printf("Bits of %d are not in alternate pattern", number);
} 출력
Bits of 4 are not in alternate pattern