С сдвиговое смещение по кругу - неожиданные результаты - PullRequest
Новая
       30

С сдвиговое смещение по кругу - неожиданные результаты

0 голосов
/ 01 марта 2019

В настоящее время я работаю над упражнениями из книги K & R C и выполняю упражнение 8 главы 2. Задача состоит в том, чтобы написать функцию «по кругу», которая вращает (или смещает по кругу) биты целого числа без знака x на n битов.Я полагаю, что нашел решение, но оно не возвращает того, чего я ожидал.Учитывая число 213, которое равно 11010101 в двоичном виде, вращение 2 битов вправо приведет к 01110101, что составляет 117.Однако, моя программа после получения x=213 и n=2 возвращает 53.Я попытался записать процесс того, что происходит с целым числом в двоичной форме в комментариях, и не могу найти проблему.Любая помощь будет оценена. 

#include <stdio.h>

unsigned rotright(unsigned x, int n)
{
    /* Example with x = 11010101 (213 in decimal), n = 2
        First iteration:
            x = (01101010) | ~(11111111 >> 1) = 11101010
        Second iteration:
            x = (01110101) | ~(11111111 >> 0) = 01110101
        Returns 01110101

    right shifts only if last bit of x == 1, then sets first bit of right shifted x to 1
    if last bit of x == 0, x is right shifted by 1 and then unchanged.

    (01101010) | ~(11111111 >> (11010101 & 00000001))
    = 01101010 | ~(11111111 >> 00000001)
    = 01101010 | 10000000 = 11101010

    (11101010) | ~(11111111 >> (11101010 & 00000001))
    = 01110101 | ~(11111111 >> 0)
    = 01110101 | 00000000 = 01110101
    */
    for (; n > 0; n--)
        x = (x >> 1) | ~(~0 >> (x & 1));
    return x;
}

int main()
{
    printf("%d\n", rotright(213, 2));
    return 0; 
}

1 Ответ

0 голосов
/ 01 марта 2019

x = (x >> 1) |~ (~ 0 >> (x & 1));

вы получите 53, потому что это (213 >> 2)

~(~0 >> (x & 1)) всегда 0, потому что ~ 0равно -1, и (-1 >> n) снова равно -1 в вашем случае, и, наконец, ~ (-1) равно 0

Вы хотите, чтобы: 

#include <stdio.h>
#include <limits.h>

unsigned rotright(unsigned x, int n)
{
   unsigned mask = (1u << (CHAR_BIT * sizeof(int) - 1));

  for (; n > 0; n--) {
    x = (x / 2) | ((x & 1) ? mask : 0);
  }
  return x;
}

int main()
{
    printf("%d\n", rotright(213, 2));
    return 0; 
}

На 32 битах результат равен 1073741877, то есть 1000000000000000000000000110101, а не 117, который предполагает, что вы работаете на 8 битах

...