Java Bit Operations (In Radix Sort)

Question

The other day I decided to write an implementation of radix sort in Java. Radix sort is supposed to be O(k*N) but mine ended up being O(k^2*N) because of the process of breaking down each digit to one number. I broke down each digit by modding (%) the preceding digits out and dividing by ten to eliminate the succeeding digits. I asked my professor if there would be a more efficient way of doing this and he said to use bit operators. Now for my questions: Which method would be the fastest at breaking down each number in Java, 1) Method stated above. 2) Convert number to String and use substrings. 3) Use bit operations.

If 3) then how would that work?

erickson · Accepted Answer · 2008-12-01 17:46:59Z

3

As a hint, try using a radix other than 10, since computers handle binary arithmetic better than decimal.

x >>> n is equivalent to x / 2ⁿ
x & (2ⁿ - 1) is equivalent to x % 2ⁿ

By the way, Java's >> performs sign extension, which is probably not what you want in this case. Use >>> instead.

answered Dec 1, 2008 at 17:46

erickson

271k59 gold badges407 silver badges502 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

deHaar · Accepted Answer · 2019-09-01 20:19:24Z

2

Radix_sort_(Java)

The line of code that does this;

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

is the bit manipulation part.

& is the operator to do a bitwise AND and >> is a right-shift.

edited Sep 1, 2019 at 20:19

deHaar

18.7k11 gold badges48 silver badges57 bronze badges

answered Dec 1, 2008 at 17:35

Lou Franco

89.4k14 gold badges137 silver badges199 bronze badges

Collectives™ on Stack Overflow

Java Bit Operations (In Radix Sort)

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related