개시하다

비트열을 정할 때, 나는 모든 비트의 상태 조합을 '서 있느냐, 서 있느냐' 라고 열거하고 싶다.
예를 들어 00100110를 입력할 때 세 자리가 서 있기 때문에 각각 서 있느냐 서 있느냐 2×3=8열의 문자열이 서 있느냐 하는 것이다.

00100110
00000110
00100010
00000010
00100100
00000100
00100000
00000000

수출을 희망하다.비트 연산서에서 같은 코드는 "어? 이거 어떻게 썼지?"매번 그렇게 생각해서 메모로 남겼어요.

설치 예

C++로 쓰면 이런 느낌이에요.

template <class T> void search(T s1, T s2) {
  if (s2 == 0) {
    show(s1);//これが列挙したいビット列
    return;
  }
  T lsb = (s2 & -s2);
  s2 ^= lsb;
  search(s1, s2);
  T s3 = s1 ^ lsb;
  search(s3, s2);
}

s1와 s2의 동일한 초기값으로 호칭할 수 있다.소스 코드는 전체적으로 이런 느낌입니다.
test.cpp

#include <cstdint>
#include <iostream>

template <class T> void show(T v) {
  size_t size = sizeof(T) * 8;
  for (size_t i = 0; i < size; i++) {
    std::cout << ((v & (1 << (size - i - 1))) ? 1 : 0);
  }
  std::cout << std::endl;
}

template <class T> void search(T s1, T s2) {
  if (s2 == 0) {
    show(s1);
    return;
  }
  T lsb = (s2 & -s2);
  s2 ^= lsb;
  search(s1, s2);
  T s3 = s1 ^ lsb;
  search(s3, s2);
}

int main() {
  uint8_t s = 38;
  search(s, s);
}

집행 예.

$ g++ test.cpp
$ ./a.out
00100110
00000110
00100010
00000010
00100100
00000100
00100000
00000000

동작 원리

search에 전달된 두 비트열 중s1은 출력할 비트열의 중간 경과를 나타내고s2는'아직 검사되지 않은 비트의 집합'을 나타낸다.search 먼저 건네준 비트열에서 이번에 꺼졌거나 남은 비트의 위치를 확인한다

T lsb = (s2 & -s2);

획득하다.(s2 & -s2)는 s2LSB를 획득한 유명한 비트 계산이다.s2에서 비트를 제거합니다.

s2 ^= lsb;

그리고 이 자리를'사라진 상황'과'없애지 않는 상황'두 가지로 나눈다.

search(s1, s2); //このビットを消さない場合
T s3 = s1 ^ lsb;
search(s3, s2); //このビットを消す場合

이렇게 돌아가면s2이 0일 때'이미 서 있는 모든 비트를 논의했기 때문에 이때s1를 출력하면 된다.
예를 들어 s=6의 경우 이렇습니다.

한 마디로 하면 스캐닝 연구의 모든 비트는 각각'해소'또는'불해소'두 가지 형식으로 나뉜다.

총결산

임의의 비트열에 대해 각 비트의 모든 조합을 열거한 코드1를 소개했다.
이것은 아주 오래 전에 누군가가 가르쳐 준 것이지만, 나는 그것이 누구인지 기억하지 못한다.아마도 헤르미 씨일 거예요. 하지만 확실한 증거가 없어요.  ↩