'마스크된' 비트셋 증가

'마스크된' 비트셋 증가

현재 트리 열거자를 작성하는 중에 다음과 같은 문제가 발생했습니다.

마스크된 비트셋, 즉 세트 비트가 마스크의 서브셋인 비트셋을 보고 있습니다.0000101가면을 쓰고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 - 1part를 지정하면 마지막 0이 아닌 비트가 0으로 변경되고 모든 하위 비트가 1로 설정됩니다.그리고나서& mask부품은 마스크 비트만 남습니다.

언급URL : https://stackoverflow.com/questions/44767080/incrementing-masked-bitsets