3
이진수가 주어지면 최하위 비트를 제거하는 가장 빠른 방법은 무엇입니까?최하위 비트 제거
01001001010 -> 01001001000
가변의 비트를 반복하는 코드에 사용된다. 가짜 코드가 뒤 따른다.
가능한 언어는 C 및 Java입니다.
A
답변
12
어 ... 예를 들어, 이미 비트의 색인을 알고 있습니다. 그럼 간단 :
bits &= ~(1 << index);
이없이 값의 위치 (최대, 최소, 또는 그 사이)의 인덱스가 index 인 비트, 마스크 오프된다. 당신은 물론 당신이 비트가 이미 설정되어 알고있는 사실을 사용하고, 분명 다시 노크하는 XOR을 사용하여 그것을 생각 해 보 니, : 아마 하나의 기계 명령어 인 반전을 저장
bits ^= (1 << index);
.
대신 인덱스를 알고없이 가장 낮은 세트 비트를 마스크하려면 트릭은 다음과 같습니다
bits &= (bits - 1);
는 예를 들어 here를 참조하십시오.
12
이것은 지금까지 내가 가진 것입니다. 누군가가 이길 수 있는지 궁금합니다.
bits &= bits-1
0
끊임없이 유용한 Bit Twiddling Hacks 어떤 algorithms for counting zero bits이있다 - 당신이 당신의 getIndexOfLowestOrderBit 기능을 구현 도움이됩니다.
필요한 비트의 위치를 알면이를 0으로 반전하는 것이 매우 간단합니다. 비트 위치, 다음, 마스크를 생성하고 반전과 원래 값 가장 낮은 순서 비트를 제거하지 않는
result = original & ~(1 << pos);
0
에 대해이 마스크를 제공. 가장 낮은 순서의 SET 비트를 0으로 만들고 싶습니다.
색인을 알고 나면 2^index와 exclusive or를 사용하면됩니다.
0
이 빠르게 비교할 경우 나도 몰라,하지만 난 그것을 작동 생각 : 자바에서
int data = 0x44A;
int temp;
int mask;
if(data != 0) { // if not there is no bit set
temp = data;
mask = 1;
while((temp&1) == 0) {
mask <<= 1;
temp >>= 1;
}
mask = ~mask;
data &= mask;
}
+0
와우! 나는 말을 잃어 버렸다. – dharga
0
는 Integer.lowestOneBit()를 사용합니다.
2
x & (~x + 1)을 사용하면 가장 낮은 세트 비트를 찾을 수 있습니다. 예 :
x: 01101100
~(x&(~x+1)): 11111011
--------
01101000
또는 x & (x - 1) 작품을 단지뿐만 아니라 쉽게 읽을 수 있습니다 :
x: 01101100
~x+1: 10010100
--------
00000100
가장 낮은 설정 비트를 지우기는 x & ~(x & (~x + 1))된다.
무엇이 가장 빠름?실행 시간, 구현 시간 또는 이해 시간? –