I am wondering if there a faster way for shuffling bits of an integer rather than the following
public int shuffleBits(int number) {
int int_width = 31;
Random random = new Random();
for(int i = 0; i < int_width; i++) {
number = swapBit(number, i, random.nextInt(int_width - i) + i);
}
}
This one won't necessarily be faster but probably give a more uniform distribution even though I didn't fully think trough it.
The basic idea is that I'm simply setting random bits until the result has the same number of bits set as the input. If you want to optimize, you could check whether ones >= Integer.SIZE / 2 and in this case, start with an integer with all bits set and successively zero them out. I doubt that this will be worth the thing, though. (Update: This optimization gives about 10 % better performance.)
public final int shuffle(final int number) {
final int ones = Integer.bitCount(number);
int result = 0;
while (Integer.bitCount(result) < ones) {
final int position = this.rnd.nextInt(Integer.SIZE);
result |= (1 << position);
}
return result;
}
I'm assuming a class member rnd of type java.util.Random. Creating a new random generator every time the function is called is a real performance killer so you don't want to do that.
Another, somewhat simpler, approach would be to simply generate uniformly distributed random integers until eventually one with the correct number of bits set is produced.
public int shuffle(final int number) {
final int ones = Integer.bitCount(number);
int result;
do {
result = this.random.nextInt();
} while (Integer.bitCount(result) != ones);
return result;
}
I have implemented a small benchmark for the code in your original post (with added swapBit function), the suggestion by @garriual and my above two versions. To be fair, I have applied the same micro-optimizations to all versions and moved creation of the Random object out of the functions.
import java.util.ArrayList;
import java.util.List;
import java.util.Random;
interface BitShuffler {
int shuffle(int number);
}
// Version by 'peter' (http://stackoverflow.com/q/28640108/1392132) with a few
// minor stylistic edits and micro-optimizations. The 'swapBit' function
// (missing in the OP) was implemented inspired by Sean Eron Anderson's "Bit
// Twiddling Hacks" (http://graphics.stanford.edu/~seander/bithacks.html).
final class Version0 implements BitShuffler {
private final Random random = new Random();
@Override
public int shuffle(int number) {
for (int i = 0; i < Integer.SIZE - 1; ++i) {
final int j = this.random.nextInt(Integer.SIZE - 1 - i) + i;
number = Version0.swapBit(number, i, j);
}
return number;
}
private static int swapBit(final int n, final int i, final int j) {
final int d = ((n >>> i) ^ (n >>> j)) & 1;
return n ^ ((d << i) | (d << j));
}
}
// Version by 'garriual' (http://stackoverflow.com/a/28640666/1392132) with a
// few minor stylistic edits and micro-optimizations.
final class Version1 implements BitShuffler {
private final Random random = new Random();
@Override
public int shuffle(int number) {
final int k = Integer.bitCount(number);
int swaps = 0;
int setBits = 0;
for (int i = 0; i < Integer.SIZE - 1 && setBits < k; ++i) {
final int j = this.random.nextInt(Integer.SIZE - 1 - i) + i;
if (Version1.bitsAreDifferent(number, i, j)) {
number ^= (1 << i) | (1 << j);
}
if (((number >> i) & 1) == 1) {
++setBits;
}
}
return number;
}
private static boolean bitsAreDifferent(final int n, final int i, final int j) {
return ((n >> i) & 1) != ((n >> j) & 1);
}
}
// Version by '5gon12eder' (http://stackoverflow.com/a/28640257/1392132) with
// additional optimization for numbers with more than half of the bits set.
final class Version2 implements BitShuffler {
private final Random random = new Random();
@Override
public int shuffle(final int number) {
final int ones = Integer.bitCount(number);
final int bits = (ones <= Integer.SIZE / 2) ? ones : Integer.SIZE - ones;
int result = 0;
while (Integer.bitCount(result) < bits) {
final int position = this.random.nextInt(Integer.SIZE);
result |= (1 << position);
}
return (ones == bits) ? result : ~result;
}
}
// Yet another version by '5gon12eder'
// (http://stackoverflow.com/a/28640257/1392132).
final class Version3 implements BitShuffler {
private final Random random = new Random();
@Override
public int shuffle(final int number) {
final int ones = Integer.bitCount(number);
int result;
do {
result = this.random.nextInt();
} while (Integer.bitCount(result) != ones);
return result;
}
}
public class Main {
// Run that many iterations per benchmark.
private static final int ITERATIONS = 10000000;
// Run each benchmark that many times to allow the JIT compiler to "warm up".
private static final int RUNS = 3;
public static void main(String[] args) {
final Random rnd = new Random();
final BitShuffler[] implementations = {
new Version0(),
new Version1(),
new Version2(),
new Version3(),
};
for (final BitShuffler impl : implementations) {
for (int i = 0; i < Main.RUNS; ++i) {
final long t1 = System.nanoTime();
int dummy = 0;
for (int j = 0; j < Main.ITERATIONS; ++j) {
final int input = rnd.nextInt();
final int output = impl.shuffle(input);
dummy ^= output; // prevent computation from being optimized away
assert Integer.bitCount(input) == Integer.bitCount(output);
}
final long t2 = System.nanoTime();
final double seconds = 1.0E-9 * (t2 - t1);
System.out.printf("%s (%08X): %5.2f s%n",
impl.getClass().getCanonicalName(),
dummy,
seconds);
}
System.out.println();
}
}
}
I get these results from running the benchmarks on my laptop.
Version0 (E53D1257): 8.79 s
Version0 (9B5AD10C): 8.85 s
Version0 (2F64EE10): 8.85 s
Version1 (B994EEFB): 10.45 s
Version1 (85F45427): 10.56 s
Version1 (351A72A6): 10.45 s
Version2 (E6A69739): 4.59 s
Version2 (B5DFC42C): 4.58 s
Version2 (816CA9A4): 4.58 s
Version3 (D42B8B0B): 7.16 s
Version3 (1FC7A303): 7.90 s
Version3 (3CB0C233): 8.33 s
I would be very wary to implement “shortcuts” in a random number generation algorithm without a thorough mathematical analysis which generally isn't easy. If you overshoot, you are likely to get a function that, very quickly, returns a poor result. I have looked at some histograms and did not find direct evidence for a defect in your version but I didn't even look at correlation diagrams. As this comparison hopefully demonstrates, faster code is not necessarily more complicated but simpler code is evidently harder to get wrong.
You can certainly optimize and improve your current approach.
(1) We want to perform a swap only if the i-th and the j-th bits are different (no need to swap if both are 0 or 1), and we can simply just do a flip on both bits. There are at most k swaps where k is the number of set bits.
(2) We can use a counter and track how many 1s that we have seen while looping and exit early as soon as we reach k.
public int shuffleBits(int number)
{
int int_width = 31;
int swaps = 0;
int K = Integer.bitCount(number);
int setBits = 0;
Random random = new Random();
for(int i = 0; i < int_width && setBits < K; i++) {
int j = random.nextInt(int_width - i) + i;
if(bitsAreDifferent(number, i, j)) {
number ^= (1 << i) | (1 << j);
}
if(((number >> i) & 1) == 1) setBits++;
}
return number;
}
private boolean bitsAreDifferent(int number, int i, int j) {
return ((number >> i) & 1) != ((number >> j) & 1);
}
