'마스킹 된'비트 세트 증가

'마스킹 된'비트 세트 증가

---

현재 다음 문제가 발생한 트리 열거자를 작성하는 중입니다.

마스크 된 비트 셋, 즉 세트 비트가 마스크의 하위 집합 인 비트 셋, 즉 0000101mask를보고 1010101있습니다. 내가 달성하고 싶은 것은 비트 세트를 증가시키는 것이지만 마스크 비트에 대해서만 가능합니다. 이 예에서 결과는입니다 0010000. 좀 더 명확하게하려면 마스킹 된 비트 만 추출합니다. 즉 0011,이를 증분하고 0100마스크 비트에 다시 배포하여 0010000.

비트 캔과 접두사 마스크의 조합을 사용하여 수동으로 작업을 구현하는 것보다 효율적인 방법을 보는 사람이 있습니까?

---

비 마스크 비트를 1로 채우면 전달됩니다.

// increments x on bits belonging to mask
x = ((x | ~mask) + 1) & mask;

---

허용되는 답변에 비해 직관적이지는 않지만 3 단계로만 작동합니다.

x = -(x ^ mask) & mask;

이것은 zch에서 제안한대로 확인할 수 있습니다.

  -(x ^ mask)
= ~(x ^ mask) + 1  // assuming 2's complement
= (x ^ ~mask) + 1
= (x | ~mask) + 1  // since x and ~mask have disjoint set bits

그러면 받아 들여진 대답과 동일 해집니다.

---

반복 순서가 그다지 중요하지 않고 감소 작업이 요구 사항을 충족 할 경우 두 가지 작업 만 사용할 수 있습니다.

시작하자

x = mask

이전 값을

x = (x - 1) & mask

x - 1부분은 0이 아닌 마지막 비트를 0으로 변경하고 모든 하위 비트를 1로 설정합니다. 그런 다음 & mask부분은 그들 사이에 마스크 비트 만 남깁니다.

참고 URL : https://stackoverflow.com/questions/44767080/incrementing-masked-bitsets