비트 Twiddling 해 킹 (좋 은 것 은 천천히 정리)

원본 주소:http://graphics.stanford.edu/~seander/bithacks.html#CopyIntegerSign
무의식중에 이 좋 은 물건 을 발 견 했 으 니 좀 보고 정리 하 자.
1. 두 개의 숫자 가 다른 지 확인 하기:
    int x,y;
   bool f= ((x^ y) <0);
2 최대 / 작은 값 취하 기
int x;  // we want to find the minimum of x and y int y;    int r;  // the result goes here  r = y ^ ((x ^ y) & -(x < y)); // min(x, y) r = x ^ ((x ^ y) & -(x < y)); // max(x, y)
글 에서 설명 을 했다.
min 을 예 로 들 면 x < y, 그러면 - (x < y) 는 전 1, r = y ^ (x ^ y) & ~ 0 = y ^ x ^ y = x
만약 x > = y 라면, - (x < y) 는 전 0, r = y ^ (x ^ y) & 0) = y
3. 한 수의 2 진법 오른쪽 연속 0 의 개 수 를 계산한다.
전에 안 드 로 이 드 소스 코드 를 볼 때 이상 한 코드 를 볼 수 있 습 니 다. a & a, 무슨 뜻 인지 모 르 겠 습 니 다. 여기 도 있 습 니 다. 차라리 자세히 연구 해 보 세 요.
나 는 100 여 개의 숫자 결 과 를 인쇄 했다 (1 부터 0 은 아무런 의미 가 없다). 그 결과 이상 한 규칙 을 발견 했다. 16 개 그룹 마다 다음 과 같은 결 과 를 나 타 낼 것 이다.
1 2 1 4 1 2 1 8 1 2 1 4 1 2 1 16 1 2 1 4 1 2 1 8 1 2 1 4 1 2 1 32 1 2 1 4 1 2 1 8 1 2 1 4 1 2 1 16 1 2 1 4 1 2 1 8 1 2 1 4 1 2 1 64 1 2 1 4 1 2 1 8 1 2 1 4 1 2 1 16 1 2 1 4 1 2 1 8 1 2 1 4 1 2 1 32 1 2 1 4 1 2 1 8 1 2 1 4 1 2 1 16 1 2 1 4 1 2 1 8 1 2 1 4 1 2 1 128 1 2 1 4 1 2 1 8 1 2 1 4 1 2 1 16 1 2 1 4 1 2 1 8 1 2 1 4 1 2 1 32 1 2 1 4 1 2 1 8 1 2 1 4 1 2 1 16 1 2 1 4 1 2 1 8 1 2 1 4 1 2 1 64 1 2 1 4 1 2 1 8 1 2 1 4 1 2 1 16 1 2 1 4 1 2 1 8 1 2 1 4 1 2 1 32 1 2 1 4 1 2 1 8 1 2 1 4 1 2 1 16 1 2 1 4 1 2 1 8 1 2 1 4 1 2 1 256 1 2 1 4 1 2 1 8 1 2 1 4 1 2 1 16 1 2 1 4 1 2 1 8 1 2 1 4 1 2 1 32 1 2 1 4 1 2 1 8 1 2 1 4 1 2 1 16 1 2 1 4 1 2 1 8 1 2 1 4 1 2 1 64 1 2 1 4 1 2 1 8 1 2 1 4 1 2 1 16 1 2 1 4 1 2 1 8 1 2 1 4 1 2 1 32 1 2 1 4 1 2 1 8 1 2 1 4 1 2 1 16 1 2 1 4 1 2 1 8 1 2 1 4 1 2 1 128 1 2 1 4 1 2 1 8 1 2 1 4 1 2 1 16 1 2 1 4 1 2 1 8 1 2 1 4 1 2 1 32 1 2 1 4 1 2 1 8 1 2 1 4 1 2 1 16 1 2 1 4 1 2 1 8 1 2 1 4 1 2 1 64 1 2 1 4 1 2 1 8 1 2 1 4 1 2 1 16 1 2 1 4 1 2 1 8 1 2 1 4 1 2 1 32 1 2 1 4 1 2 1 8 1 2 1 4 1 2 1 16 1 2 1 4 1 2 1 8 1 2 1 4 1 2 1 512 1 2 1 4 1 2 1 8 1 2 1 4 1 2 1 16 1 2 1 4 1 2 1 8 1 2 1 4 1 2 1 32 1 2 1 4 1 2 1 8 1 2 1 4 1 2 1 16 1 2 1 4 1 2 1 8 1 2 1 4 1 2 1 64 1 2 1 4 1 2 1 8 1 2 1 4 1 2 1 16 1 2 1 4 1 2 1 8 1 2 1 4 1 2 1 32 1 2 1 4 1 2 1 8 1 2 1 4 1 2 1 16 1 2 1 4 1 2 1 8 1 2 1 4 1 2 1 128 1 2 1 4 1 2 1 8 1 2 1 4 1 2 1 16 1 2 1 4 1 2 1 8 1 2 1 4 1 2 1 32 1 2 1 4 1 2 1 8 1 2 1 4 1 2 1 16 1 2 1 4 1 2 1 8 1 2 1 4 1 2 1 64 1 2 1 4 1 2 1 8 1 2 1 4 1 2 1 16 1 2 1 4 1 2 1 8 1 2 1 4 1 2 1 32 1 2 1 4 1 2 1 8 1 2 1 4 1 2 1 16 1 2 1 4 1 2 1 8 1 2 1 4 1 2 1 256 1 2 1 4 1 2 1 8 1 2 1 4 1 2 1 16 1 2 1 4 1 2 1 8 1 2 1 4 1 2 1 32 1 2 1 4 1 2 1 8 1 2 1 4 1 2 1 16 1 2 1 4 1 2 1 8 1 2 1 4 1 2 1 64 1 2 1 4 1 2 1 8 1 2 1 4 1 2 1 16 1 2 1 4 1 2 1 8 1 2 1 4 1 2 1 32 1 2 1 4 1 2 1 8 1 2 1 4 1 2 1 16 1 2 1 4 1 2 1 8 1 2 1 4 1 2 1 128 1 2 1 4 1 2 1 8 1 2 1 4 1 2 1 16 1 2 1 4 1 2 1 8 1 2 1 4 1 2 1 32 1 2 1 4 1 2 1 8 1 2 1 4 1 2 1 16 1 2 1 4 1 2 1 8 1 2 1 4 1 2 1 64 1 2 1 4 1 2 1 8 1 2 1 4 1 2 1 16 1 2 1 4 1 2 1 8 1 2 1 4 1 2 1 32 1 2 1 4 1 2 1 8 1 2 1 4 1 2 1 16 1 2 1 4 1 2 1 8 1 2 1 4 1 2 1 1024 1 2 1 4 1 2 1 8 1 2 1 4 1 2 1 16 1 2 1 4 1 2 1 8 1 2 1 4 1 2 1 32 1 2 1 4 1 2 1 8 1 2 1 4 1 2 1 16 1 2 1 4 1 2 1 8 1 2 1 4 1 2 1 64 1 2 1 4 1 2 1 8 1 2 1 4 1 2 1 16 1 2 1 4 1 2 1 8 1 2 1 4 1 2 1 32 1 2 1 4 1 2 1 8 1 2 1 4 1 2 1 16 1 2 1 4 1 2 1 8 1 2 1 4 1 2 1 128 1 2 1 4 1 2 1 8 1 2 1 4 1 2 1 16 1 2 1 4 1 2 1 8 1 2 1 4 1 2 1 32 1 2 1 4 1 2 1 8 1 2 1 4 1 2 1 16 1 2 1 4 1 2 1 8 1 2 1 4 1 2 1 64 1 2 1 4 1 2 1 8 1 2 1 4 1 2 1 16 1 2 1 4 1 2 1 8 1 2 1 4 1 2 1 32 1 2 1 4 1 2 1 8 1 2 1 4 1 2 1 16 1 2 1 4 1 2 1 8 1 2 1 4 1 2 1 256 1 2 1 4 1 2 1 8 1 2 1 4 1 2 1 16 1 2 1 4 1 2 1 8 1 2 1 4 1 2 1 32 1 2 1 4 1 2 1 8 1 2 1 4 1 2 1 16 1 2 1 4 1 2 1 8 1 2 1 4 1 2 1 64 1 2 1 4 1 2 1 8 1 2 1 4 1 2 1 16 1 2 1 4 1 2 1 8 1 2 1 4 1 2 1 32 1 2 1 4 1 2 1 8 1 2 1 4 1 2 1 16 1 2 1 4 1 2 1 8 1 2 1 4 1 2 1 128 1 2 1 4 1 2 1 8 1 2 1 4 1 2 1 16 1 2 1 4 1 2 1 8 1 2 1 4 1 2 1 32 1 2 1 4 1 2 1 8 1 2 1 4 1 2 1 16 1 2 1 4 1 2 1 8 1 2 1 4 1 2 1 64 1 2 1 4 1 2 1 8 1 2 1 4 1 2 1 16 1 2 1 4 1 2 1 8 1 2 1 4 1 2 1 32 1 2 1 4 1 2 1 8 1 2 1 4 1 2 1 16 1 2 1 4 1 2 1 8 1 2 1 4 1 2 1 512
보 셨 죠? 앞 에 15 개가 똑 같 아 요. 마지막 에 그 숫자 가 달라 요. 마지막 숫자 만 보면 8 개 씩 똑 같 아 요. 앞 에 7 개가 똑 같 아 요. 마지막 에 달라 요. 그리고 마지막 숫자 를 관찰 해 보 세 요. 규칙 은:
128 256 128 512 128 256 128  1024
128 256 128 512 128 256 128  2048
128 256 128 512 128 256 128  1024
128 256 128 512 128 256 128  4096
그리고 마지막 열 수 를 보 세 요.
1024 2048 1024 4096 1024 2048 1204 8192
1024 2048 1024 4096 1024 2048 1024 16384
보 셨 죠? 여전히 8 개 팀 이 한 팀 입 니 다. 마지막 열 수 는 8 개 팀 이 될 것 이 라 고 추측 할 수 있 습 니 다.이거 말고 재 밌 다.
자, 본론 으로 돌아 갑 니 다. v & v 의 역할 은 오른쪽 에서 연속 적 인 0 과 처음으로 나타 난 1 을 꺼 내 는 것 입 니 다.
그리고 코드 보기:
4. 567913. 우 리 는 v 말미 에 처음으로 1 이 나타 난 수 를 num, 즉 v & v 로 만 들 었 다.
첫 번 째 if, num 이 0 이 아니라면 많아야 31 개 0,
두 번 째 if, 판단 후 두 바이트, 0 이 아니라면 앞의 두 바이트 도 의미 가 없 기 때문에 16 을 뺀 다.
3 번 째 if 는 마지막 바이트 가 0 이 아니라면 꼴찌 2 번 째 바이트 도 의미 가 없 으 므 로 8 을 빼 면 앞 뒤 가 대칭 적 이 므 로 주의해 야 한다. 모든 if 가 반 으로 줄 어 든 판단 이 므 로 첫 번 째 if 가 실행 되 지 않 을 가능성 이 높 기 때문에 뒤의 바이트 를 판단 할 때 반드시 앞의 대칭 을 맞 춰 야 한다.
마지막 두 if 는 반반 의 판단 이 고 마지막 바이트 이 므 로 더 이상 설명 할 필요 가 없다.
작가 님 대 박!!!