Java 비트 작업 (Radix 정렬)

Question

다른 날에 나는 구현을 작성하기로 결정했다. radix 정렬 자바에서. Radix 정렬은 O (k*n)이어야하지만 각 숫자를 하나의 숫자로 분해하는 과정 때문에 광산은 O (k^2*n)가되었습니다. 나는 앞의 숫자를 modding (%)으로 분해하고 후속 숫자를 제거하기 위해 10으로 나누어 냈습니다. 나는 교수에게 더 효율적인 방법이 있는지 물었고 비트 연산자를 사용한다고 말했다. 이제 내 질문의 경우 : Java에서 각 숫자를 분류하는 데 가장 빠른 방법, 1) 위에 언급 된 방법. 2) 숫자를 문자열로 변환하고 하위 문자열을 사용하십시오. 3) 비트 작업을 사용하십시오.

만약 3) 그러면 어떻게 작동할까요?

Answer 1

힌트로, 컴퓨터는 10 진수 산술을 더 잘 처리하므로 10 이외의 라디습니다.

• x >>> n은 x / 2와 같습니다^N
• x & (2^N -1)는 x % 2에 해당합니다^N

그건 그렇고, Java의 >>는 사인 확장을 수행하는데,이 경우이 경우 원하는 것이 아닐 것입니다. 대신 >>> 사용하십시오.

Answer 2

[http://en.literateprograms.org/Radix_sort_(Java)](http://en.literateprograms.org/radix_sort_(java))))

이를 수행하는 코드 라인;

 int key = (a[p] & mask) >> rshift;

비트 조작 부분입니다.

& 운영자는 약간의 작업을 수행하고 >>는 올바른 편이입니다.