Деление на степень 2 с использованием сдвига битов

Question

У меня есть следующая задача:

Вычислить x/(2^n), для 0 <= n <= 30 с использованием битового сдвига.

Требование: округление до нуля.

Примеры:

divpwr2(15,1) = 7
divpwr2(-33,4) = -2

Юридические операторы: ! ~ & ^ | + << >>

Максимальное количество операторов: 15

Вот что у меня так далеко:

public int DivideByPowerOf2(int x, int n)
{
    //TODO: find out why DivideByPowerOf2(-33,4) = -3 instead of -2
    return x >> n;
}

DivideByPowerOf2(15,1) = 7 в порядке.

Но DivideByPowerOf2(-33,4) = -3 вместо -2.Почему?

Answer 1

После поиска хорошего ответа я наткнулся на это и смог получить рабочий фрагмент.Позвольте мне помочь объяснить это другим, которые могут найти это в будущем.

(x + ((x >> 31) & ((1 << n) + ~0))) >> n

Этот фрагмент кода является тем, что вы ищете, как опубликовано Sotelo.Причина, по которой это работает, очень важна, особенно для вас, чтобы понять вашу домашнюю работу.Во-первых, вы должны полностью понимать представление дополнения 2.Это когда самый старший бит используется для смещения всего двоичного представления на соответствующую степень 2. Если мы отображаем только 32 бита (стандартно для большинства процессоров), то мы можем использовать сдвиг вправо (>>) для перемещения наиболее значимогобит до наименее значимого бита.При этом вы сделаете арифметический сдвиг вправо, который будет копировать этот старший значащий бит (1, если он отрицательный) во всем представлении битового уровня.В 6-битном двоичном представлении это приведет либо к

000000
111111

. Это позволит нам в дальнейшем работать с целым числом, чтобы определить некоторые свойства.Сначала нам нужно найти степень 2, на которую мы собираемся разделить (в данном случае n), и сдвинуть двоичный код в эту позицию, затем минус 1. Например, давайте используем степень 3 или 8.

(000001 << 3) -1
000111

теперь, когда у нас есть оба этих двоичных представления, мы будем и их вместе

111111 & 000111 = 000111 (case 1)
000000 & 000111 = 000000 (case 2)

теперь, учитывая, что x нечетно или четно (случай 1 и случай 2 соответственно), мы можем добавить к этому x и получитьчисло, которое является совершенной степенью 2 (если мы разделим на степень 2, мы получим правильный ответ).Ниже приведено несколько примеров с x = 8, 10, -8, -12 соответственно.

001000 + 000000 = 001000
001010 + 000000 = 001010
now for the negatives that plague you
111000 + 000111 = 111111
110100 + 000111 = 111011

Теперь последний шаг - разделить эти числа на нашу степень n.Для деления на 8 это затем 3, как указано выше.

001000 >> 3 = 000001 or 1 in decimal (8/8 = 1)
001010 >> 3 = 000001 or 1 in decimal (10/8 = 1 because of truncation)
111111 >> 3 = 111111 or -1 in decimal (-8/8 = -1)
111011 >> 3 = 111111 or -1 in decimal (-12/8 = -1 because of truncation)

Итак, у вас это есть.Ваша первая задача - найти отрицательный или положительный результат, а затем получить бит от отрицательного, который соответствует вашей степени 2 -1.Добавьте это к вашему x, чтобы получить вашу степень 2 делимого числа в двоичном виде.Затем, наконец, разделите правильное изменение вашей силы на два.

Answer 2

Обратите особое внимание на поведение при округлении.

• / (целочисленное деление) всегда округляется до нуля.
• Что делает сдвиг битов?
• Как вы можете компенсировать эту разницу?

Answer 3

Отрицательные числа оказываются единичными в двоичном представлении из-за представления дополнения их двух.Возможно, чтение о дополнении до двух поможет.

Answer 4

public int DivideByPowerOf2(int x, int n)
    {

        return (x + ((x >> 31) & ((1 << n) + ~0))) >> n;
    }