Побитовый оператор для простого переворачивания всех битов в целое число? - PullRequest
Новая
       99

Побитовый оператор для простого переворачивания всех битов в целое число?

43 голосов
/ 15 июня 2011

Я должен перевернуть все биты в двоичном представлении целого числа.Дано: 

10101

Выходные данные должны быть 

01010

Каким побитовым оператором это достигается при использовании с целым числом?Например, если бы я писал такой метод, как int flipBits(int n);, что было бы в теле?Мне нужно перевернуть только то, что уже присутствует в числе, а не все 32 бита в целом числе.

Ответы [ 13 ]

0 голосов
/ 27 марта 2014

Поскольку от нас требуется только перевернуть минимальные биты, требуемые для целого числа (скажем, 50 равно 110010, а при инвертировании становится 001101, что равно 13), мы можем инвертировать отдельные биты по одному от младшего разряда к старшему разряду и продолжайте сдвигать биты вправо и соответственно применяйте степень 2. Код ниже выполняет необходимую работу: 

int invertBits (int n) {
        int pow2=1, int bit=0;
            int newnum=0;
            while(n>0) {
              bit = (n & 1);
              if(bit==0)
                  newnum+= pow2;
              n=n>>1;
              pow2*=2;
          }
          return newnum;
        }
0 голосов
/ 18 апреля 2013

У меня есть другой способ решить этот случай, 

public static int complementIt(int c){
 return c ^ (int)(Math.pow(2, Math.ceil(Math.log(c)/Math.log(2))) -1);
}

Он использует XOR для получения бита дополнения, для его дополнения нам нужно XOR данных с 1, например:

101 XOR 111 = 010

(111 - это «ключ», он генерируется путем поиска в «n» квадратном корне данных)

, если вы используете ~ (дополнить)результат будет зависеть от его типа переменной, если вы используете int, то он будет обрабатываться как 32-битный.

0 голосов
/ 15 июня 2011

Я должен был бы увидеть некоторые примеры, чтобы быть уверенным, но вы можете получить неожиданные значения из-за арифметики с двумя дополнениями. Если число имеет начальные нули (как в случае с 26), оператор ~ перевернет их, чтобы сделать их ведущими, что приведет к отрицательному числу.

Одним из возможных путей решения этой проблемы является использование класса Integer: 

int flipBits(int n){
    String bitString = Integer.toBinaryString(n);
    int i = 0;

    while (bitString.charAt(i) != '1'){
        i++;
    }

    bitString = bitString.substring(i, bitString.length());

    for(i = 0; i < bitString.length(); i++){
        if (bitString.charAt(i) == '0')
            bitString.charAt(i) = '1';
        else
            bitString.charAt(i) = '0';
    }

    int result = 0, factor = 1;

    for (int j = bitString.length()-1; j > -1; j--){
        result += factor * bitString.charAt(j);
        factor *= 2;
    }

    return result;
}

У меня сейчас не настроена среда Java для тестирования, но это общая идея. По сути, просто преобразуйте число в строку, обрежьте начальные нули, переверните биты и преобразуйте его обратно в число. Класс Integer может даже иметь какой-то способ разобрать строку в двоичное число. Я не знаю, нужно ли так решать проблему, и, возможно, это не самый эффективный способ сделать это, но это даст правильный результат.

Редактировать: ответ полигенубрикантов на этот вопрос также может быть полезным

Страница:
...