Блог

Я пытаюсь вычислить эквивалентные выражения следующих уравнений, используя побитовые операторы сложения и / или вычитания. Я знаю, что должен быть ответ (который, кроме того, обобщается для работы с любым модулем 2 ^ a-1, где a — степень 2), но по какой-то причине я не могу понять, какова связь.

Начальные выражения:

 x = n % (2^32-1);
c = (int)n / (2^32-1); // ints are 32-bit, but x, c, and n may have a greater number of bits
  

Моя процедура для первого выражения заключалась в том, чтобы взять значение по модулю 2 ^ 32, затем попытаться компенсировать разницу между двумя значениями по модулю. У меня возникли проблемы со второй частью.

 x = n amp; 0xFFFFFFFF   difference // how do I calculate difference?
  

Я знаю, что разница n%(2^32)-n%(2^32-1) является периодической (с периодом 2^32*(2^32-1) ), и есть «всплеск», начинающийся с кратных 2^32-1 и заканчивающийся на 2^32 . После каждого 2^32 кратного значения график разницы уменьшается на 1 (надеюсь, мои описания имеют смысл)

Аналогично, второе выражение может быть вычислено аналогичным образом:

 c = n >> 32   makeup // how do I calculate makeup?
  

Я думаю, что состав постоянно увеличивается на 1 при кратности 2^32-1 (и уменьшается на 1 при кратности 2^32 ), хотя у меня возникают проблемы с выражением этой идеи в терминах доступных операторов.

Вы можете использовать эти идентификаторы:

 n mod (x - 1) = (((n div x) mod (x - 1))   ((n mod x) mod (x - 1))) mod (x - 1)
n div (x - 1) = (n div x)   (((n div x)   (n mod x)) div (x - 1))
  

Первое происходит из (ab c) mod d = ((a mod d) (b mod d) (c mod d)) mod d .

Второе происходит от расширения n = ax b = a(x-1) a b при делении на x-1 .

Я думаю, что нашел ответ на свой вопрос:

Сначала вычислите c, затем используйте результаты для вычисления x. Предполагается, что сравнение возвращает 1 для true, 0 для false. Кроме того, все сдвиги являются логическими сдвигами.

 c = (n>>32)   ((t amp; 0xFFFFFFFF) >= (0xFFFFFFFF - (n>>32)))

x = (0xFFFFFFFE - (n amp; 0xFFFFFFFF) - ((c - (n>>32))<<32)-c) amp; 0xFFFFFFFF
  

редактировать: изменен x (нужно сохранить только младшие 32 бита, остальное — «мусор»)