Подсчитайте количество кратных против каждой мощности 4

Question

Учитывая число, n, мне нужно эффективно найти, сколько раз это число кратно всем степеням 4 меньше заданного числа.

Примеры:

• 16 является кратным 4, и 16, так что результат будет 2.
• 64 является кратным 4, 16 и 64, так что результат будет 3.
• 256 является кратным 4, 16, 64 и 256, так что результат будет 4.
• 14 не кратно любой степени 4, так что результат будет 0.
• 35 не кратен любой мощности 4, поэтому результат будет равен 0.

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

power = 4; 
while (power < n) { 
    result += !(n & (power - 1)); 
    power *= 4; 
} 

Answer 1

Вы можете использовать логарифмы. Быстрый поиск Google для «fast log2 C++» привел довольно длинный список идей. Тогда ваш ответ будет log2 (x)/2, и вам нужно будет найти способ убедиться, что ваш результат будет целым числом, если вам нужен только ответ для точной степени 4.

Если вы программируете для процессора x86 вы можете использовать BitScanForward & BitScanReverse, чтобы найти установленный бит и использовать его для вычисления log2. Следующий код работает в Visual Studio, для GCC или других, есть другие способы сделать встроенную сборку.

uint32_t exact_power_of_4_scan(uint32_t num) 
{ 
    unsigned long reverse; 
    unsigned long forward; 

    if (!_BitScanReverse(&reverse, num)) return 0; 
    _BitScanForward(&forward, num); 

    if (reverse != forward) return 0; // makes sure only a single bit is set 
    if (reverse & 0x1) return 0; // only want every other power of 2 
    return reverse/2; 
} 

Если вам требуется переносное решение, поиск таблицы может быть способом, но сложнее.

uint8_t not_single_bit[256] = { 
    1, 0, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 
    0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 
    0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 
    0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 
    0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 
}; 

uint8_t log2_table[256] = { 
    0, 0, 1, 0, 2, 0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 
    4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
    5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
    6, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
    7, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 
}; 

uint32_t exact_power_of_2(uint32_t num) 
{ 
    auto a = not_single_bit[num & 0xff]; 
    auto b = not_single_bit[(num >> 8) & 0xff]; 
    auto c = not_single_bit[(num >> 16) & 0xff]; 
    auto d = not_single_bit[(num >> 24) & 0xff]; 

    if (a + b + c + d != 3) { 
    return 0; 
    } 

    if (!a) { 
    return log2_table[num & 0xff]; 
    } 
    if (!b) { 
    return log2_table[(num >> 8) & 0xff] + 8; 
    } 
    if (!c) { 
    return log2_table[(num >> 16) & 0xff] + 16; 
    } 

    return log2_table[(num >> 24) & 0xff] + 24; 
} 

uint32_t exact_power_of_4(uint32_t num) 
{ 
    auto ret = exact_power_of_2(num); 

    if (ret & 0x1) return 0; 
    return ret/2; 
} 

Оба являются линейными алгоритмами. Первый, вероятно, будет бить цикл для почти любого значения num, но я его не тестировал. Второй, вероятно, только хорош для довольно больших num s.

Answer 2

Математика была бы не держать деления 4 до результата больше не делится на 4.

Если вы действительно хотите сделать это с помощью побитовых операций, методы here могут быть использованы для подсчета числа конечных нулевых бит (то есть числа, когда значение делится на 2). Они могут быть скорректированы для подсчета пар конечных битов (т. Е. Делимости на 4, а не на 2).

Обратите внимание, что вам необходимо будет использовать значения unsigned, чтобы избежать определенных случаев неопределенного или неуказанного поведения.

Я бы оспаривал ваше утверждение, что побитовые операции сделают более эффективное решение. Это не задание без тестирования, особенно с современными компиляторами.