본문 바로가기
반응형

bit21

C, C++ - 1 비트 개수 세기 (Bit Counter) C, C++ 전체 링크 삼성 C형 전체 링크 주어진 숫자에 대해 비트 단위로 1이 몇 개 인지 세는 함수를 만들어보자. 먼저 비트 단위로 출력하기를 이용하여 아래의 코드를 실행해보자. #include #include using namespace std; typedef long long int ll; template void printBitNumber(T number) { unsigned int bitSize = sizeof(number) * 8; T mask = (1ull) = 1; if (i % 8 == 7) printf(" "); } putchar('\n'); } int main(void) { ll bit = 1234123412341234123; printf("bit : "); printBitNumb.. 2023. 7. 29.
C, C++ - 비트 연산으로 2의 제곱수 처리하기 C, C++ 전체 링크 삼성 C형 전체 링크 2n 또는 2n - 1 판단하기. 숫자 x에서 -1을 하고 & 연산을 해서 0이 되면 2n이다. 그리고 x에서 +1을 하고 & 연산을 해서 0이 되면 2n - 1이다. 2n은 bit로 나타내면 하나의 bit만 1이기 때문에 이런 규칙이 생긴다. 0100 0000 = 64 0011 1111 = 63 ------------------ 0000 0000 = 64 & 63 = 0 마찬가지로 2n - 1도 연산을 해보면 쉽게 규칙을 파악할 수 있다. 0111 1111 = 127 1000 0000 = 128 ------------------- 0000 0000 = 127 & 128 = 0 #include int main(void) { int x; /* 주어진 부호 없는 .. 2023. 7. 29.
C, C++ - 임시 변수 없이 변수 바꾸기 (Swap Two Numbers without using the Third Variable) C, C++ 전체 링크 삼성 C형 전체 링크 long long int 타입 a, b 변수를 교체해보자. #include typedef long long int ll; int main(void) { ll a = 1234123412341234; ll b = 5678567856785678; printf("a : %lld\n", a); printf("b : %lld\n", b); putchar('\n'); ll tmp = a; a = b; b = tmp; printf("a : %lld\n", a); printf("b : %lld\n", b); return 0; } 값이 잘 변경된 것을 알 수 있다. XOR Swap 알고리즘을 이용하면 변수를 추가하지 않고 아래와 같이 간결하게 두 변수를 교환할 수 있다. a ^.. 2023. 7. 29.
C, C++ - 비트 연산 기본 매크로 함수 (bit macro : get, set, clear, toggle, check) C, C++ 전체 링크 삼성 C형 전체 링크 비트 연산 기본에 대해서 알아보자. (get, set, clear, toggle, check) - 비트 1개 연산 - 연속된 여러 비트 연산 - 비트 마스크 연산 비트 1개 연산 다음의 코드를 실행시켜보자. #include typedef long long int ll; #define SET_BIT(value, n) ((value) |= (1ull 2023. 7. 29.
C, C++ - 비트 단위로 출력하기 (Print Bit) C, C++ 전체 링크 삼성 C형 전체 링크 아래와 같이 %x 옵션을 이용하면 4비트 (0 ~ F)로 값을 출력할 수 있다. #include typedef unsigned long long int ull; int main(void) { ull h = 1023; printf("0x%08X\n", h); return 0; } 이제 변수가 주어질 때, 1 비트 단위로 출력하는 함수를 만들어보자. printBitNumber를 템플릿을 이용해서 만들고 mask를 이용해 최상위 비트부터 하나씩 내려가면서 출력한다. // signed에서 error 발생 #include typedef unsigned char uc; typedef unsigned short us; typedef unsigned int ui; typed.. 2023. 6. 3.
비트 on / off C, C++ 전체 링크 삼성 C형 전체 링크 참고 - 비트 단위로 출력하기 구현은 아래를 참고하자. #include template void printBitNumber(T number) { unsigned int bitSize = sizeof(number) * 8; T mask = (1ull) = 1; if (i % 8 == 7) printf(" "); } putchar('\n'); } int main(void) { int x; printf("제일 오른쪽 1-비트 끄기 (ex: 01011000 => 01010000)\n"); x = 2152; printBitNumber(x); x &= (x - 1); printBitNumber(x); printf("===============================.. 2023. 1. 24.
유일한 수 두개 알고리즘 문제 전체 링크 judge.koreatech.ac.kr/problem.php?id=1074 유일한 수 문제의 응용 버전이다. 모든 수가 짝이 있으나 단 2개의 수만 짝이 없다. 유일한 수 문제대로 풀면 짝이 있는 수는 자연스럽게 제거할 수 있지만, 짝이 맞지 않는 두 수가 xor 연산되어 있어서 답을 구할 수 없게 될 것 같다. 하지만 여전히 xor 연산을 이용해서 문제를 해결할 수 있다. 먼저 두 수가 다르다는 것은, 최소 1 bit가 다르다는 뜻이 된다. 즉, 모든 N을 xor한 후, 어떤 다른 1 bit를 기준으로 1 bit가 있는 경우는 on에 xor을 1 bit가 없는 경우는 off에 xor을 하면 두 수가 분리된다. 예를 들어서 두 수가 3과 7이라고 하자. 0011(3)과 0111(.. 2021. 3. 1.
C, C++ - 최하위 / 최상위 비트 구하기 (Find MSB, LSB) C, C++ 전체 링크 삼성 C형 전체 링크 참고 - 비트 단위로 출력하기 다음과 같은 비트가 있다고 가정하자. 0010 0000 1100 0010 그러면 최하위 비트(Least Significant Bit)와 최상위 비트(Most Significant Bit)는 아래와 같다. 0010 0000 1100 0010 0000 0000 0000 0010 → 2 : 최하위 비트 (LSB : Least Significant Bit) 0010 0000 0000 0000 → 8192 : 최상위 비트 (MSB : Most Significant Bit) 최하위 비트 구하기 최하위 비트 추출법은 매우 간단하다. int lsb = x & (-x); // int lsb = x & (~x + 1) 2의 보수를 구하는 방법이기도.. 2021. 3. 1.
유일한 수 알고리즘 문제 전체 링크 judge.koreatech.ac.kr/problem.php?id=1007 문제의 조건을 보면 홀수개의 숫자가 입력이 되고, 그 중 단 하나만 다르다. 따라서 bit 연산 ^(xor)을 누적하면 단 하나의 숫자만 남게 된다. 어떤 숫자 N에 숫자 M bit를 반전시키고, 다시 M bit를 반전 시키면 N이 되기 때문이다. ( N = N ^ M ^ M ) 따라서 0부터 시작해서 누적하면 짝이 있는 숫자들은 자연스레 사라지게 된다. #include int T, N; int main(void) { scanf("%d", &T); for (int tc = 0; tc < T; tc++) { int ans; scanf("%d", &N); ans = 0; for (int i = 0; i < N.. 2021. 3. 1.
반응형

티스토리툴바