본문 바로가기

Algorithms/simulation90

Bit Reverse 0x12 => 0x48 이것이 Bit Reverse 00010010 => 01001000 - unsigned char 일 때는 lookup table 로 만들어 두고 - 규칙성을 활용하여 recursive 형식으로 풀이함 #include typedef unsigned char u8; typedef unsigned short u16; typedef unsigned int u32; const u8 byte_rev_table[256] = { 0x00, 0x80, 0x40, 0xc0, 0x20, 0xa0, 0x60, 0xe0, 0x10, 0x90, 0x50, 0xd0, 0x30, 0xb0, 0x70, 0xf0, 0x08, 0x88, 0x48, 0xc8, 0x28, 0xa8, 0x68, 0xe8, 0x18, 0x.. 2021. 4. 13.
Hamming Weight 4 - 코드는 쉬운데 - 시간 복잡도는 불리함 - 비트 수가 현저히 적을 때 좋음 #include const int m1 = 0x55555555; const int m2 = 0x33333333; const int m4 = 0x0f0f0f0f; const int m8 = 0x00ff00ff; const int m16 = 0x0000ffff; const int h01 = 0x01010101; int popcount_d(int x) { int count; for (count=0; x; count++) x &= x - 1; return count; } int main() { int bitmap = 0x10000000; int count; count = popcount_d(bitmap); printf("count=%.. 2021. 4. 13.
Hamming Weight 3 - version 2에서 8, 16, 0x7f 가 바뀌었음 - h01가 0x01010101; 이므로 이것을 곱한다음에 >>24를 하면 됨 #include const int m1 = 0x55555555; const int m2 = 0x33333333; const int m4 = 0x0f0f0f0f; const int m8 = 0x00ff00ff; const int m16 = 0x0000ffff; const int h01 = 0x01010101; int popcount_c(int x) { x -= (x >> 1) & m1; x = (x & m2) + ((x >> 2) & m2); x = (x + (x >> 4)) & m4; return (x * h01) >> 24; } int __sw_hweight32(in.. 2021. 4. 13.
Hamming Weight 2 - 연산자의 숫자를 줄임 - 필요한 부분만 연산해서 나감 - 마지막에 0x7f 로 하여 필요한 비트만 추출함 #include const int m1 = 0x55555555; const int m2 = 0x33333333; const int m4 = 0x0f0f0f0f; const int m8 = 0x00ff00ff; const int m16 = 0x0000ffff; const int h01 = 0x01010101; int popcount_b(int x) { x -= (x >> 1) & m1; x = (x & m2) + ((x >> 2) & m2); x = (x + (x >> 4)) & m4; x += x >> 8; x += x >> 16; return x & 0x7f; } int main() { int .. 2021. 4. 13.
Hamming Weight 1 - int = 0x12345678 일 때. 이 때 비트가 1인 개수 찾기 - O(32) -> O(5) = O(logN) 으로 시간을 줄 일 수 있음. - 2비트 끼리, 4비트 끼리, 8비트 끼리, 16비트 끼리, 32비트 단위로 계산을 하여 1의 갯수를 구할 수 있음 #include const int m1 = 0x55555555; const int m2 = 0x33333333; const int m4 = 0x0f0f0f0f; const int m8 = 0x00ff00ff; const int m16 = 0x0000ffff; const int h01 = 0x01010101; int popcount_a(int x) { x = (x & m1 ) + ((x >> 1) & m1 ); x = (x & m2 ) + (.. 2021. 4. 13.
find first set / find next bit char 타입의 경우 8비트(1바이트) 데이터 저장이 가능함. 해당 비트의 1 / 0 여부를 파악 할 수 있어야 하고, 하나의 데이터 타입을 넘어선다면, 다음 배열에서의 비트에 추가하면 됨. 메모리, 시간 관련하여 최적화 하는데 필요함. 비트 연산 &, >> 그림으로 그려서 이해하면 어렵지 않음. #if 1 #include #define BITS_PER_LONG 64 unsigned long __ffs(unsigned long word) { int num = 0; #if BITS_PER_LONG == 64 if ((word & 0xffffffff) == 0) { num += 32; word >>= 32; } #endif if ((word & 0xffff) == 0) { num += 16; word >>=.. 2021. 4. 13.
테트리스 테트리스 제한시간: 1000 ms 메모리제한: 256 MB 3 * 3 크기의 2차원 테이블에 일부 테트리스 유형뿐만 아니라 아래 그림과 같이 하나 이상의 셀이 채워진 블록이 주어진다. 이 블록을 쌓아갈때 가로줄이 모두 채워지면 그 가로줄은 삭제된다. 주어진 모든 블록을 쌓은 후 최종적으로 남은 블록중 최대 높이를 구하는 프로그램을 작성하시오. 블록 정보에서 채워진 곳은 1, 비어있는 곳은 0으로 표시된다. 첫 번째 줄에 테트리스의 가로줄의 크기 N과 블록의 개수 M이 주어진다. (3 = i - 3; j--) { if (tet[j] == P) { for (k = j; k 2020. 1. 10.
테트리스 테트리스 제한시간: 1000 ms 메모리제한: 256 MB 3 * 3 크기의 2차원 테이블에 일부 테트리스 유형뿐만 아니라 아래 그림과 같이 하나 이상의 셀이 채워진 블록이 주어진다. 이 블록을 쌓아갈때 가로줄이 모두 채워지면 그 가로줄은 삭제된다. 주어진 모든 블록을 쌓은 후 최종적으로 남은 블록중 최대 높이를 구하는 프로그램을 작성하시오. 블록 정보에서 채워진 곳은 1, 비어있는 곳은 0으로 표시된다. 첫 번째 줄에 테트리스의 가로줄의 크기 N과 블록의 개수 M이 주어진다. (3 = i - 3; j--) { if (tet[j] == P) { for (k = j; k 2020. 1. 10.
진법 변환 진법 변환 제한시간: 1000 ms 메모리제한: 64 MB A진법 수 N을 입력 받아 B진법 수로 출력하는 프로그램을 작성하시오. N에 사용되는 값은 0 ~ 9, A ~ Z이다. (2 2020. 1. 10.

티스토리툴바