Знайти найближчий ступінь двійки

Задача

Написати найефективнішим способом функцію що для заданого x повертає таке число n що 2^(k-1) <= n < 2^k. Ішими словами функція має повертати наступну за заданим числом ступінь двійки.

Рішення

Ідея полягає в тому щоб розкопіювати найстаршу одиницю в усі біти і додати 1 – так ми отримаємо наступну ступінь двійки. Хоча ми і не знаємо де наступна одиниця, проте можемо зробити наступне (для 4-байтового значення):

1. копіюємо старші 2 біти в молодші – тепер у нас 2 копії найстаршої одиниці

2. зверху накладаємо ті самі біти але зсунуті на один байт вправо – маємо 4 копії

3. зверху накладаємо ті ж біти але зсунуті на 4 біти вправо – маємо 8 копій

4. повторюємо для зсува в 2 і 1 біт – маємо найстаршу одиницю встановлену у всих наймолодших бітах

5. додамо 1 – маємо наступну ступінь двійки, бо це буде лише одна одиниця на всі біти.

Рішення не враховує переповнення.

int NearestPowerOf2(int x) 
{
    –x;   
     x |= x >> 1;
    x |= x >> 2;    
    x |= x >> 4;    
    x |= x >> 8;    
    x |= x >> 16;    
    return ++x;
}

Один коментар для “Знайти найближчий ступінь двійки”

Залишити відповідь