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

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

Вычислить 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. Почему?

Ответы

Ответ 1

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

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

Этот фрагмент кода - это то, что вы ищете, как опубликовано Sotelo. Причина, по которой она работает, очень важна, особенно для вас, чтобы понять вашу домашнюю работу. Сначала вы должны полностью понимать представление 2-х долей. Это когда самый старший бит используется для смещения всего двоичного представления на соответствующую мощность 2. Если мы изображаем только 32 бита (стандартный в большинстве процессоров), то мы можем использовать правый сдвиг ( → ), чтобы переместить самый старший бит в младший значащий бит. При этом вы будете делать арифметический сдвиг вправо, который скопирует этот самый старший бит (a 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 (если мы делим на степень по два, мы получим правильное ответ). Ниже приведено несколько примеров с 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 делимых чисел в двоичном формате. Затем, наконец, разделите вас на правый сдвиг вашей силы на два.

Ответ 2

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

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

Ответ 3

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

Ответ 4

public int DivideByPowerOf2(int x, int n)
    {

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