특정 수의 비트 세트로 여러 숫자를 만듭니다

StackOverflow https://stackoverflow.com/questions/506807

문제

문제

32 비트 숫자를 만들어야합니다 (서명 또는 서명되지 않은 것은 중요하지 않습니다. 가장 높은 비트는 어쨌든 설정되지 않습니다). 각 숫자에는 주어진 숫자가 있어야합니다.

순진한 솔루션

가장 쉬운 솔루션은 물론 0 수로 시작하는 것입니다. 루프 내에서 숫자가 1 씩 증가하고, 카운트가 원하는 값을 갖는 경우, 루프가 반복되는 경우 숫자가 목록에 저장됩니다. 충분한 숫자가 발견되면 루프가 중지됩니다. 물론 이것은 잘 작동하지만 원하는 비트 수가 매우 높아지면 끔찍하게 느립니다.

더 나은 솔루션

5 비트 세트를 갖는 가장 간단한 숫자는 처음 5 비트가 설정된 숫자입니다. 이 숫자는 쉽게 만들 수 있습니다. 루프 내에서 첫 번째 비트가 설정되고 숫자가 왼쪽으로 이동됩니다. 이 루프는 5 번 실행되며 5 비트 세트로 첫 번째 숫자를 찾았습니다. 다음 몇 가지 숫자도 쉽게 만들 수 있습니다. 우리는 이제 숫자가 비트 폭이 6 인 척하고 가장 높은 숫자는 설정되지 않았습니다. 이제 우리는 첫 번째 제로 비트를 오른쪽으로 이동하기 시작하므로 1011111111111111111111111111111111111, 111011, 111101, 111110을 얻습니다. 다른 0을 전면에 추가 하고이 과정을 반복하여 반복 할 수 있습니다. 0111110, 1011110, 1101110.

그렇다면 다음 숫자가 얼마나 많은 비트를 가질 수 있는지, 세트가 필요한 세트 비트 수에 관계없이 가능한 모든 순열, 일반적인 접근 방식을 만들 수있는 더 좋은 방법이 있습니까?

도움이 되었습니까?

해결책

당신은 사용할 수 있습니다 Hackersdelight.org의 Bit-Twiddling Hack.

그의 저서에는 동일한 숫자 1 비트 세트로 다음 더 높은 숫자를 얻는 코드가 있습니다.

이것을 원시로 사용하여 숫자를 늘리면 시작점을 찾는 것입니다. N 비트 세트로 첫 번째 숫자를 얻는 것은 쉽습니다. 단지 2^(N -1) -1입니다.

당신은 모든 가능한 숫자를 매우 빨리 반복 할 것입니다.

  unsigned next_set_of_n_elements(unsigned x) 
  {
     unsigned smallest, ripple, new_smallest, ones;

     if (x == 0) return 0;
     smallest     = (x & -x);
     ripple       = x + smallest;
     new_smallest = (ripple & -ripple);
     ones         = ((new_smallest/smallest) >> 1) - 1;
     return ripple | ones;
  }

  // test code (shown for two-bit digits)

  void test (void)
  {
    int bits = 2;
    int a = pow(2,bits) - 1;
    int i;

    for (i=0; i<100; i++)
    {
       printf ("next number is %d\n", a);
       a = next_set_of_n_elements(a);
    }
  }

다른 팁

반대 방향으로 문제에 접근하려고 시도하십시오. N 범위 0-31 "의 숫자.

4 숫자를 찾으려고한다고 가정 해 봅시다. [0,1,2,3]부터 시작한 다음 매번 마지막 숫자를 늘리십시오 ([0,1,2,4], [0,1,2,5] ...) 한계에 도달 할 때까지 [0,1,2,31]. 그런 다음 두 번째 숫자를 늘리고 마지막 숫자를 1로 설정하십시오 : [0,1,3,4]. 마지막 숫자를 늘리는 것으로 되돌아 가십시오 : [0,1,3,5], [0,1,3,6] ... 등이 끝나면 [0,1,4로 돌아갑니다. , 5] - 결국 [0,1,30,31]에 도달 한 시점에서 한 단계 더 뒤로 트랙해야합니다. 마침내 [28,29,30,31]로 끝날 때까지 계속하십시오.

숫자 세트가 주어지면 32 비트 숫자로 변환하는 것은 쉽습니다.

조합을 생성하려고합니다. 이것을 참조하십시오 위키 백과 기사.

accassadic 순열 (Google On) 또는 알고리즘 중 하나가 필요합니다. 위키

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top