비트수가 같은 다음 수(Next Higher or Lower Number with same number of binary bits set)

제목을 번역하는게 참 애매해서 영어도 같이 써놨습니다.

5 (101) 를 예로 들면

다음 큰 수는 6이고 (110)

이전 작은 수는  3이 됩니다. (11)

Next higher number with same number of binary bits set

View more PowerPoint from GowriKumar Chandramouli

알고리즘 설명은 따로 안하겠습니다.

위의 프리젠테이션을 보시면 이해하실 수 있습니다.

저 프리젠테이션에 추가적으로 내용을 덧붙이자면

x의 Next Higher Number를 구하는 함수를

snoob(x)라고하면

x의 Next Lower Number는 ~snoob(~x) 를 쓰면 나옵니다.

(단, 1,3,7,15,31 과 같이 구할 수 없는 수 같은 경우는 -1이 나오게 됩니다.)

그리고 프리젠테이션에 나온 함수를

줄여 쓰고 싶다면 다음과 같이 쓸 수 있습니다.

template<typename _T>

_T snoob(_T x)

{

return (x+(x&-x))|(((x^(x+(x&-x)))>>2)/(x&-x));

}