Давайте сначала немного перепишем это, потому что нет необходимости в Queues, или в массиве tmp и т. Д. Шаг первый, класс-заглушка, который позволяет нам писать меньше кода:
private class Numlist extends ArrayList<Integer> {
Numlist() { super(); }
}
Готово, мыбольше не нужно писать ArrayList<Integer> везде.
Теперь java делает "автобокс", поэтому все, что вы храните в Integer, может делать int, и наоборот.Это удобно, потому что мы можем выбросить все эти строки.Нам это не нужно, если мы просто заботимся о битовом сравнении:
public void sort(Numlist numbers) {
// No copying `numbers` to a `tmp` queue: just work with it directly.
Numlist zeroes, ones;
for (int k = 1; k < 32; k++) {
// Build this step's masking value, which we can use to
// find the value of individual bits by using bitwise AND.
// Also note that we _know_ this is a safe integer operation.
mask = (int) Math.pow(2,k);
// just allocate new lists; it's about as fast as clearing.
zeroes = new Numlist();
ones = new Numlist();
// "scatter": now we empty the numbers list one element at a
// time, and then we'll fill it back up after we emptied it.
while (!numbers.isEmpty()) {
int e = numbers.remove(0);
if ((e & mask) == mask) {
ones.add(e);
} else {
zeroes.add(e);
}
}
// "gather"
for (int i: zeroes) { numbers.add(i); }
for (int i: ones) { numbers.add(i); }
}
}
И с этим переписыванием все работает.Мы удалили много многословия, что облегчает рассуждения о том, что делает код, и мы удалили целое «int to string to substring, затем char char», что означает, что намного меньше ошибиться.
С точки зрения тестирования, добавьте свою функцию в следующий класс:
import java.lang.Math;
import java.util.ArrayList;
public class Test {
// private class goes here
public static void main(String[] argv) { new Test(); }
public Test() {
Numlist list = new Numlist();
list.add(10);
list.add(77810);
list.add(4);
list.add(100);
list.add(1);
list.add(290387423);
list.add(23423);
sort(list);
System.out.println(list);
}
// function goes here
}
И готово: javac с радостью скомпилирует ее, а выполнение должно дать [1, 4, 10, 100, 23423, 77810, 290387423]
Вы такжеобратите внимание, что мы не используем for (int k = 31; k > 0; k--), но мы используем for (int k=1; k<32; k++) ... почему?Это имеет значение?
это имеет огромное значение
Запустив нашу маску от b000 ... 001 до b100 ... 000, мы гарантируем, что несмотря на "выбирая значения обратно ", их относительное" упорядочение "меньше текущего бита" сохраняется.
Если мы запустим нашу маскировку другим способом, от b1000 ... 000 до b000 ... 001, то на каждом шаге мы отменяем порядок, который мы только что установили, и результат не сортируетсясписок вообще: [1, 4, 100, 77810, 10, 290387423, 23423]
** edit **: почему маскирование работает?
Целочисленные типы byte, char, int и long простобитовые комбинации 1, 2, 4 и 8 байтов соответственно, поэтому все они уже являются «двоичными числами», нам просто нужен способ доступа к отдельным битам, который мы можем сделать, используя побитовое маскирование .
Чтобы замаскировать «все, кроме определенного бита», вы можете использовать побитовое И некоторого битового шаблона и шаблон, в котором установлен только один бит, который мы действительно можем создать легко , поскольку это просто числа, которые являются «степенями 2».
Например, чтобы проверить биты в числе 23, мы можем использовать следующие проверки:
23 & 1 2 4 8 16 32
b0 1 & 1=1 0=0 0=0 0=0 0=0 0=0
b1 1 & 0=0 1=1 0=0 0=0 0=0 0=0
b2 1 & 0=0 0=0 1=1 0=0 0=0 0=0
b3 0 & 0=0 0=0 0=0 1=0 0=0 0=0
b4 1 & 0=0 0=0 0=0 0=0 1=1 0=0
b5 0 & 0=0 0=0 0=0 0=0 0=0 1=0
Здесь мы видим число 23, двоичное 10111 и результат маскирования каждой степенью двойки: 23 и 1 дают 1, поэтому мы знаем, что установлен первый бит.Мы видим, что 23 и 2 дают 2, поэтому мы знаем, что установлен второй бит.То же самое для 4, но 23 и 8 дают 0. Мы знаем, что четвертый бит установлен , а не .
Таким образом, мы можем проверить битовую комбинацию любой длины, используя побитовое AND: if (number & mask) == mask мы знаем, что бит для этой маски установлен.Если результат равен 0, мы знаем, что бит не был установлен.
Также обратите внимание, что & равно , а не так же, как &&: & является побитовым Иоперация, выполняющая AND для каждого бита между левой и правой частью оператора.Оператор && - это логический AND, требующий логических значений для левой и правой сторон.Логика «И» фактически является «одним И», тогда как побитовое «И» - это «столько операций И, сколько есть битов для проверки».