부호없는 int가 주어지면, set bit의 "index"를 얻는 가장 빠른 방법은 무엇입니까?

Question

예를 들어. 0110은 비트 1과 2가 설정되어 있고, 1000은 비트 3이 설정되어 있습니다. 1111은 비트 0,1,2,3을 가지고 있습니다.

Answer 1

나는 루프에서 최하위 비트를 테스트하고 테스트 할 것입니다. 그것은 32 비트 마스크 (또는 unsigned int가 어떤 길이이든)를 사용하는 것이 더 빠릅니다.

/앨런

Answer 2

for(int i = 0; variable ; ++i, variable >>= 1) { 
    if(variable & 1) 
    // store bit index - i 
} 

Answer 3

는에 의해 빠른 무엇을 의미하는지에 따라 다릅니다.

"간단한 코드 작성"을 의미하는 경우 .NET에서 BitArray 클래스를 사용하고 각 비트를 부울 true/false로 참조 할 수 있습니다.

BitArray Class

Answer 4

만 4 비트 정말이있는 경우, 다음 가장 빠른 방법은 확실히 조회 테이블을 포함한다. 결국 16 개의 다른 가능성이 있습니다.

Answer 5

@Allan 바람 ...

여분의 비트 교대는 필요하지 않습니다. 최하위 비트를 비교하는 것이 두 번째 최하위 비트를 비교하는 것만 큼 효율적이기 때문에 비트 시프트를하지 않는 것이 더 효율적입니다. 약간의 교대 작업도 필요한 비트 연산을 두 배로 늘리는 것입니다.

firstbit = (x & 0x00000001) 
secondbit = (x & 0x00000002) 
thirdbit = (x & 0x00000004) //<-- I'm not saying to store these values, just giving an example. 
... 

어쨌든 그래서 하나의 비트가 32 비트 비교만큼이나 효율적 것이다 비교, 32 비트 레지스터로 완료 x86 시스템에서 모든 작업.

루프 자체가 발생하는 오버 헤드는 말할 것도 없습니다.

문제는 일정한 코드 행에서 수행 할 수 있으며 코드가 x86 또는 x64에서 실행되는지 여부에 관계없이 더 효율적입니다.

Answer 6

모든 비트 해킹에 대한 인터넷

최저 기준-bit twiddling hacks

당신은 INT의 바이트를 반복의 하이브리드 접근 방식을 취할 수

Answer 7

에 설정된 비트의 인덱스를 결정하기 위해 조회 테이블을 사용 각 바이트 (니블로 분해). 그런 다음 정수에 위치를 반영하기 위해 인덱스에 오프셋을 추가해야합니다.

즉, 32 비트 정수의 MSB로 시작했다고 가정 해 보겠습니다. 상위 니블 인덱스는 upper_idxs라고 부르며 하위 니블 인덱스는 lower_idxs라고 부릅니다. 그런 다음 lower_idxs의 각 요소에 24를 추가하고 upper_idxs의 각 요소에 28을 추가해야합니다. 다음 바이트는 비슷하게 처리되지만, 오프셋은 각각 16 및 20이 될 것이고, 그 이유는 그 바이트가 8 비트 "다운"이기 때문이다.

는 나에게이 방법은 타당하지만 .NET 있었다면 나는 입증 잘못 :-)

Answer 8

에 행복 할 것입니다 그리고 당신은 내가 좋은 유창 인터페이스를 원하는 그것을 많이 사용해야 할 것이다.

다음 클래스를 만들 것입니다 (BitTools라는 이름에 완전히 만족하지는 않습니다).

[Flags] 
public enum Int32Bits 
{ 
    // Lookup table but nicer 
    None = 0, 
    Bit1 = 1,  Bit2 = 1 << 1, Bit3 = 1 << 2, Bit4 = 1 << 3, Bit5 = 1 << 4, Bit6 = 1 << 5, Bit7 = 1 << 6, Bit8 = 1 << 7, 
    Bit9 = 1 << 8, Bit10 = 1 << 9, Bit11 = 1 << 10, Bit12 = 1 << 11, Bit13 = 1 << 12, Bit14 = 1 << 13, Bit15 = 1 << 14, Bit16 = 1 << 15, 
    Bit17 = 1 << 16, Bit18 = 1 << 17, Bit19 = 1 << 18, Bit20 = 1 << 19, Bit21 = 1 << 20, Bit22 = 1 << 21, Bit23 = 1 << 22, Bit24 = 1 << 23, 
    Bit25 = 1 << 24, Bit26 = 1 << 25, Bit27 = 1 << 26, Bit28 = 1 << 27, Bit29 = 1 << 28, Bit30 = 1 << 29, Bit31 = 1 << 30, Bit32 = 1 << 31, 
} 

public static class BitTools 
{ 
    public static Boolean IsSet(Int32 value, Int32Bits bitToCheck) 
    { 
     return ((Int32Bits)value & bitToCheck) == bitToCheck; 
    } 

    public static Boolean IsSet(UInt32 value, Int32Bits bitToCheck) 
    { 
     return ((Int32Bits)value & bitToCheck) == bitToCheck; 
    } 

    public static Boolean IsBitSet(this Int32 value, Int32Bits bitToCheck) 
    { 
     return ((Int32Bits)value & bitToCheck) == bitToCheck; 
    } 
    public static Boolean IsBitSet(this UInt32 value, Int32Bits bitToCheck) 
    { 
     return ((Int32Bits)value & bitToCheck) == bitToCheck; 
    } 
} 

그리고 당신이 그것을 사용할 수있는 다음과 같은 방법 : 다른 지능 * 비트 열거하고는 isset과 IsBitSet의 올바른 오버로드를 만들 수있는 각 (U) 지능 크기

static void Main(string[] args) 
{ 
    UInt32 testValue = 5557; //1010110110101; 

    if (BitTools.IsSet(testValue, Int32Bits.Bit1)) 
    { 
     Console.WriteLine("The first bit is set!"); 
    } 
    if (testValue.IsBitSet(Int32Bits.Bit5)) 
    { 
     Console.WriteLine("The fifth bit is set!"); 
    } 
    if (!testValue.IsBitSet(Int32Bits.Bit2)) 
    { 
     Console.WriteLine("The second bit is NOT set!"); 
    } 
} 

.

EDIT : 내가 잘못 읽고, 당신은 서명되지 않은 ints에 대해 이야기하고 있지만,이 경우에는 동일합니다.

Answer 9

두 단계 :

1. 추출 설정 set_bit= x & -x; x&= x - 1;

2. 빼기 1 계산 비트마다 설정된 비트.

Answer 10

가 나는

import java.util.*; 
public class bitSet { 

    public static void main(String[]args) { 
     Scanner scnr = new Scanner(System.in); 
     int x = scnr.nextInt(); 
     int i = 0; 
     while (i<32) { 
      if (((x>>i)&1) == 1) { 
       System.out.println(i); 
      } 
      i++; 
     } 
    } 
}