두 개의 bit열에서 동일한 최대길이 prefix 뽑아내기
글쓴이: raymundo / 작성시간: 월, 2013/07/29 - 1:24오전
안녕하세요,
아주 긴 비트열이 아니라 그냥 int 범위에 충분히 들어가는 두 수가 있을 때 이진수로 나타냈을 때 공통되는 프리픽스만 뽑아내려고 하는데요.
10111011 PA 10110010 PB -------- 10110000 P0 - 구하고자 하는 것 (P: Prefix 부분, A,B: 나머지 뒷부분, 0: 00...0, 1: 11...1)
prefix 뒷부분이 완전히 서로 반대라면 (B == ~A) 그냥 AND 연산만 한 번 하면 P0 형태가 되겠습니다만,
위에처럼 어떤 자리는 동일하게 1일 수도 있는 경우라면요.
제가 생각한 건
1011 1???
XOR 1011 0???
---------------
0000 1??? => X (달라지기 시작한 부분의 XOR은 반드시 1이니까)
ceil( log2(X) ) = 3 => w (달라지는 부분의 비트 수를 구하고)
2^(w+1) - 1 = 1111 => mask (그 자리만큼 1로 채운 마스크를 만들고)
PA AND (NOT mask) = P0 (mask를 반전한 후 둘 중 하나에 AND하면 P 부분만 남음)위와 같은데요, 제가 지금 비트연산만으로 가능한 것을 상당히 어렵게 하고 있는 게 아닌가 싶은데 잠은 오고 검색은 의외로 잘 안 되고
(아주 긴 비트어레이나 문자열 이런 얘기만 자꾸 검색되네요) 해서 조언을 구하고자 합니다.
Forums:
앗 floor 연산을 해놓고 저걸 ceil이라고
앗 floor 연산을 해놓고 저걸 ceil이라고 적었군요. 역시 졸려서.. =ㅅ=
좋은 하루 되세요!
...
정수연산하면서 log2를 쓰는 건 완전 삽질이고요... (일단 rounding error가 안 일어난다는 보장이 없으니 결과가 맞으리라고 장담할 수 없습니다. 모든 케이스를 하나씩 다 따져보면 어쩌면 될지도 모르겠습니다만...)
x86에는 bsr (bit scan reverse)라는 명령어가 있습니다. 안타깝게도 C 표준 라이브러리에는 이를 지원하는 기능이 없는 것 같지만 찾아보니 이런 내용이 있네요:
http://stackoverflow.com/questions/2589096/find-most-significant-bit-left-most-that-is-set-in-a-bit-array
아 저 글타래는 저도 예전에 봤었던 기억이 이제야
아 저 글타래는 저도 예전에 봤었던 기억이 이제야 나네요.
일단 log2 대신에 저기 언급된 방법을 써서 w를 구하도록 해야겠군요.
감사합니다 :-)
그렇지만 여전히 w를 구해서 마스크를 새로 만드는 방법 말고 뭔가 비트와이즈 연산만으로
방법이 없을까 미련이 남는데 주먹구구로 AND OR NOT 조합해보면서 우연히 찾게 되길
바라는 건 무리 같고, 저런 걸 논리적으로 풀지를 못하겠네요.
또는 '방법 없음' 증명을 할 수 있다면 미련없이 포기하겠는데...
좋은 하루 되세요!
A와 B를 XOR연산하고, 다시 그걸 NOT으로
A와 B를 XOR연산하고, 다시 그걸 NOT으로 뒤집으면 prefix부분은 모두 1로 가득차 있겠죠. 이걸 w라고 하고, 어레이처럼 나타내서 n번째 자리 비트를 w[n]이라고 해 봅시다
이제 첫번째 0부터 모두 0으로 만들면 되는데요
w2[i] = w2[i-1]*w[i] for i>1
이렇게 찾은 w2는 일단 0이 한번 나오면 그 뒤로 계속 0이 됩니다.
그 다음 w2를 마스크로 써서 원래의 A나 B에 AND연산을 하면 됩니다.
recursive한 답이긴 한데요, 이걸 비트 연산으로 어떻게 바꿀지는 아직은 생각이 안납니다.
피할 수 있을때 즐겨라! http://melotopia.net/b
이런 방법도 있군요. 한번 0이 되면 계속 0이 되는
이런 방법도 있군요. 한번 0이 되면 계속 0이 되는 건 좋은 생각입니다.
그런데 한비트씩 루프를 돌면서 계산할 거면 그냥 처음부터 두 비트열의 첫자리부터 비교하면서 가면 그만일 듯 싶기도... ^^;
좋은 하루 되세요!
네. 그게 문제입니다. -_-;
네. 그게 문제입니다. -_-;
피할 수 있을때 즐겨라! http://melotopia.net/b
clz (혹은 fls) 을 응용하면
clz (혹은 fls) 을 응용하면 되겠는데요.
fls 나 clz 가 있는 아키텍쳐라면 w 구하는 것은 일도 아니고,
없는 아키텍쳐거나 generic 을 원한다면... clz 를 약간 변형해서 mask 를 직접 구해도 되고요.
#include <stdio.h> #include <stdio.h> #include <stdlib.h> static unsigned int mlz(register unsigned int x) { if (!x) return 0xffffffff; register unsigned int e = 0xfffffffe; if (x & 0xFFFF0000) { e <<=16; x >>=16; } if (x & 0x0000FF00) { e <<= 8; x >>= 8; } if (x & 0x000000F0) { e <<= 4; x >>= 4; } if (x & 0x0000000C) { e <<= 2; x >>= 2; } if (x & 0x00000002) { e <<= 1; } return e; } int main(int argc, char **argv) { const unsigned int PA = strtoul(argv[1], NULL, 0); const unsigned int PB = strtoul(argv[2], NULL, 0); const unsigned int P0 = PA & mlz(PA ^ PB); printf("%08X\n%08X\n%08X\n", PA, PB, P0); return 0; }shift(특히 left) 와 rotate 를 구분하지 않는 아키텍쳐는 조심.
One option is using a table
One option is using a table with 32 entry. An i'th entry has a value with first i bits 1, the rest 0.
After the XOR and NOT operation, do an AND operation with an entry in the table and check if it is equivalent to that entry.
You can just iterate the entries sequentially, or you can do a binary search.
확인이 늦었습니다. 답글 주신 두 분
확인이 늦었습니다. 답글 주신 두 분 감사합니다.
결국 마스크 자체를 두 수의 비트와이즈 연산만으로 구하는 건 안 될 듯 하네요.
좋은 하루 되세요!
댓글 달기