Округление целое, используя бит вертел

Question

Есть ли способ, чтобы «усечение» целое число, используя бит вертел, как будто пол разделены и затем умножают обратно, как:

z = floor(x/y) * y 

Я знаю, что это можно сделать так что если y имеет степень двойки, например:

z = floor(x/4) * 4 == x & ~3 

Но что трюк делает один использовать, когда y некоторое общее положительное целое число?

Answer 1

Для каждого отдельного y, существует последовательность операций (сложение, вычитание, сдвиг и бинарные), который делит x на y быстрее, чем (x86) инструкции деления. Нахождение этой последовательности, однако, не является простым и должно быть сделано заранее (возможно, если вы разделите на то же самое yмного).

Простой пример: разделить произвольный uint32x на 3, мы можем вместо того, чтобы рассчитать x * M в uint64 типа и сдвиг вправо на 33 бит, где M является волшебной константой, равной 2 /3 закругленных .

Следующий код (С) пытается 20 случайных uint32 значения с выше алгоритма и проверяет, что результат равен просто разделив на 3:

#include <stdio.h> 
#include <stdlib.h> 
#include <time.h> 

int main() 
{ 
    int step; 
    unsigned x, y1, y2; 
    unsigned const M = (1ULL << 33)/3 + 1; 
    srand (time (NULL)); 
    for (step = 0; step < 20; step++) 
    { 
     x = (rand() << 30) | (rand() << 15) | rand(); 
     y1 = x/3; 
     y2 = (x * 1ULL * M) >> 33; 
     printf ("%10u %10u %10u %s\n", x, y1, y2, y1 == y2 ? "true" : "false"); 
    } 
    return 0; 
} 

Для получения дополнительной информации см Delight книга Хакера в целом, и свободно доступное дополнение - глава 10 здесь: hackersdelight.org/divcMore.pdf.

Answer 2

Причина, по которой это работает для полномочий 2, заключается в том, как работают двоичные представления. Разделение на 2 (или степень 2) идентично сдвигу бит. Сдвиг вправо, а затем назад оставил ту же сумму, что и слово-деление, как вы выразились.

Рассмотрите произвольный двоичный номер: 110101010111. Если вы поменяете его на 3 раза вправо (деление на 8), а затем снова верните его, то он будет равен 110101010000, который идентичен ИДЕНТИФИКАЦИИ с 111111111000. Теперь давайте рассмотрите деление на 3 из десятичного числа 16: начните с 10000. Разделение (без сдвига!) на 3 будет равно 5 (101), а умножить на 3 снова будет 15 (1111). Никакое смещение бит не может этого сделать.

Answer 3

Очевидное, что нужно сделать, это конвертировать в любую базу, с которой вы пытаетесь работать, а затем в основном сделать последнюю цифру 0. (Или, если вы работаете с k-й мощностью, тогда сделайте последние k цифр 0) , Однако вы спросили о бит (base-2). Оказывается, что для любой желаемой базы B (по крайней мере, это нечетно) вы можете найти число в двоичном формате, чтобы первые M-цифры в базе B были любыми, что вы хотите, для любого M. Таким образом, как вы могли возможно, есть общий метод для того, что вы хотите (с нечетной базой), который работает только на битах (двоичных)? По крайней мере, это было бы намного сложнее, чем просто преобразование вашего номера в нужную базу и установление всех последних цифр на 0 и последующее преобразование в натуральное целочисленное представление base-2.