Вращение бита в C

Question

Проблема: Упражнение 2-8 языка программирования C: «Напишите функцию rightrot (x, n), которая возвращает значение целого числа x, повернутого вправо на n позиций».

Я сделал это всеми способами, которые я знаю, как.Вот проблема, которая у меня возникла.Возьмите определенное число для этого упражнения, скажем, 29, и поверните его вправо на одну позицию.
11101, и оно станет 11110 или 30. Скажем, ради аргумента, что система, над которой мы работаем, имеет размер целого типа без знака:32 битаДалее, скажем, что число 29 хранится в целочисленной переменной без знака.В памяти число будет иметь 27 нулей впереди.Поэтому, когда мы поворачиваем 29 вправо, используя один из нескольких алгоритмов, которые мои опубликованы ниже, мы получаем число 2147483662. Это явно не желаемый результат.

unsigned int rightrot(unsigned x, int n) {
    return (x >> n) | (x << (sizeof(x) * CHAR_BIT) - n);
}

Технически, это правильно, но я думалчто 27 нулей перед 11101 были незначительными.Я также попробовал несколько других решений:

int wordsize(void) {    // compute the wordsize on a given machine...
    unsigned x = ~0;
    int b;
    for(b = 0; x; b++)
        x &= x-1;
    return x;
}

unsigned int rightrot(unsigned x, int n) {
    unsigned rbit;
    while(n --) {
        rbit = x >> 1;
        x |= (rbit << wordsize() - 1);
    }
    return x;

Это последнее и последнее решение, где я думал, что оно у меня есть, я объясню, где оно не получилось, как только я доберусь до конца.Я уверен, что вы увидите мою ошибку ...

int bitcount(unsigned x) {
    int b;
    for(b = 0; x; b++)
        x &= x-1;
    return b;
}

unsigned int rightrot(unsigned x, int n) {
    unsigned rbit;
    int shift = bitcount(x);
    while(n--) {
        rbit = x & 1;
        x >>= 1;
        x |= (rbit << shift);
    }
}

Это решение дает ожидаемый ответ 30, который я искал, но если вы используете число для x, как, скажем, 31 (11111), то есть проблемы, в частности, результат 47, используя один для п.Я не думал об этом раньше, но если используется число типа 8 (1000), тогда хаос.В 8 есть только один установленный бит, поэтому сдвиг, скорее всего, будет неправильным.Моя теория на данный момент заключается в том, что первые два решения верны (в основном), и я просто что-то упускаю ...

Answer 1

Побитовое вращение всегда обязательно в пределах целого числа данной ширины. В этом случае, поскольку вы предполагаете 32-битное целое число, 2147483662 (0b10000000000000000000000000001110) действительно является правильным ответом; Вы не делаете ничего плохого!

0b11110 не будет считаться правильным результатом при любом разумном определении, так как продолжение его правильного поворота с использованием того же определения никогда не вернет вам исходные данные. (Учтите, что другой поворот вправо даст 0b1111, а продолжение вращения не будет иметь никакого эффекта.)

Answer 2

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

Независимо от моего убеждения, книга еще не ввела оператор sizeof в разделе 2.9, поэтому единственный способ определить размер шрифта - подсчитать биты."от руки".

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

Использование только тех частей языка, которые рассматриваются в книге, дораздел 2.9, вот моя реализация (с целочисленными параметрами, возвращающими целое число, как указано в упражнении): цикл n раз, x >> 1 каждая итерация;если старый младший бит x был 1, установите новый старший бит.

int rightrot(int x, int n) {
    int lowbit;

    while (n-- > 0) {
        lowbit = x & 1;            /* save low bit */
        x = (x >> 1) & (~0u >> 1); /* shift right by one, and clear the high bit (in case of sign extension) */
        if (lowbit)
            x = x | ~(~0u >> 1);   /* set the high bit if the low bit was set */
    }

    return x;
}

Answer 3

int bitcount(unsigned x) {
    int b;
    for(b = 0; x; b++)
        x &= x-1;
    return b;
}

unsigned rightrot(unsigned x,int n) {
   int b = bitcount(x);
   unsigned a = (x&~(~0<<n))<<(b-n+1);
   x>> = n;
   x| = a;
}

Answer 4

Вы можете найти местоположение первого '1' в 32-битном значении, используя двоичный поиск. Затем запишите бит в позиции LSB, сдвиньте значение вправо на требуемое количество мест и поместите бит LSB в позицию первого «1».