Функция битов в Radix-сортировке

Question

Radix-sort - ключи сортировки в виде чисел, представленных в базе М-числа. Чтобы использовать сортировку Radix, мне нужно понять функцию битов.

unsigned bits(int x, int k, int j)
{ return (x >> k) & ~(~0 << j); }

Согласно прочитанному мною документу, он говорит:

. Он вычисляет j битов, которые появляются k битов из справа от x.

, но он слишком короткий и есть какой-то символ, который я едва понимаю (например, >>, ~ и &). Я попытался проверить это, и он возвращает только два значения 0 и 1. Мне действительно нужно объяснение об этом и его реальной функции

Answer 1

В функции unsigned bits(int x, int k, int j), x - это значение, которое нужно отсортировать, k - это самая правая позиция битов для извлечения из x, а j - это количество битов, из которых нужно извлечь x.

Если вы хотите выполнить радикальную сортировку с 4-битными значениями, вы должны установить j на 4, а k на значение 0, затем 4, 8, et c.

Функция работает следующим образом. Во-первых, он сдвигается x на k бит справа. Это делается с помощью выражения (x >> k).

Другое выражение - (~0 << j). ~0 инвертирует все биты значения 0. Это дает значение со всеми битами равным 1. Затем это значение сдвигается влево на j бит. Затем вы получите значение со всеми битами, равными 1, и j, самые правые биты равны 0.

Это значение снова инвертирует все его биты из-за оператора ~ перед (~0 << j). Затем вы получите значение со всеми битами, установленными в 0, и для j правых крайних битов, установленных в 1.

Это значение затем объединяется с операцией и с результатом первого выражения x >> k. С помощью операции and все биты с нулем обнуляются. Поскольку во втором выражении все биты равны 0, кроме j менее значимого. В результате все биты устанавливаются в 0, кроме j менее значимого (наиболее правого).

Окончательный результат - вернуть j бит со смещением k в значение x.

Если, например, биты x равны 100101001 и k равно 3, а j равно 3, результат будет 0000000101.

Это двоичный эквивалент извлечения a ди git из числа.