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

Ответ 1

Унарный оператор ~ - побитовое отрицание. Если вам нужно меньше бит, чем то, что подходит в int, тогда вам нужно будет замаскировать его с помощью & после факта.

Ответ 2

Просто используйте побитовый оператор ~.

int flipBits(int n) {
    return ~n;
}

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

int flipBits(int n, int k) {
    int mask = 1;
    for(int i = 1; i < k; ++i)
        mask |= mask << 1;

    return ~n & mask;
}

Edit2: Просто увидел, что этот вопрос для Java.. думал, что он для C! Отредактировано.

Edit3: Как предложил Lưu Vĩnh Phúc, можно создать маску как (1 << k) - 1 вместо использования цикла.

int flipBits2(int n, int k) {
    int mask = (1 << k) - 1;
    return ~n & mask;
}

Ответ 3

Существует несколько способов перевернуть весь бит с помощью операций

x = ~x; // has been mentioned and the most obvious solution.
x = -x - 1; or x = -1 * (x + 1);
x ^= -1; or x = x ^ ~0;

Ответ 4

Хорошо, так как до сих пор существует только одно решение, которое дает "правильный" результат, и это... действительно не очень хорошее решение (используя строку для подсчета ведущих нулей, которая будет преследовать меня в моих мечтах;))

Итак, вот мы идем с хорошим чистым решением, которое должно работать - не проверили его, хотя, но вы получите суть. Действительно, java, не имеющий неподписанного типа, крайне раздражает такие проблемы, но он должен быть достаточно эффективным (и если я могу сказать, что MUCH более элегантный, чем создание строки из числа)

private static int invert(int x) {
    if (x == 0) return 0; // edge case; otherwise returns -1 here
    int nlz = nlz(x);
    return ~x & (0xFFFFFFFF >>> nlz);
}

private static int nlz(int x) {
    // Replace with whatever number leading zero algorithm you want - I can think
    // of a whole list and this one here isn't that great (large immediates)
    if (x < 0) return 0;
    if (x == 0) return 32;
    int n = 0;
    if ((x & 0xFFFF0000) == 0) {
        n += 16;
        x <<= 16;
    }
    if ((x & 0xFF000000) == 0) {
        n += 8;
        x <<= 8;
    }
    if ((x & 0xF0000000) == 0) {
        n += 4;
        x <<= 4;
    }
    if ((x & 0xC0000000) == 0) {
        n += 2;
        x <<= 2;
    }
    if ((x & 0x80000000) == 0) {
        n++;
    }       
    return n;
}

Ответ 5

быстрее и проще:

/* inverts all bits of n, with a binary length of the return equal to the length of n
k is the number of bits in n, eg k=(int)Math.floor(Math.log(n)/Math.log(2))+1
if n is a BigInteger : k= n.bitLength();
*/
int flipBits2(int n, int k) {
    int mask = (1 << k) - 1;
    return n ^ mask;
}

Ответ 6

Мне нужно будет увидеть некоторые примеры, но вы можете получать неожиданные значения из-за двух арифметических дополнений. Если число имеет ведущие нули (как в случае 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 может даже иметь некоторый способ разбора строки в двоичном числе. Я не знаю, как это должно быть сделано, и это, вероятно, не самый эффективный способ сделать это, но это приведет к правильному результату.

Изменить: ответ polygenlubricants на этот вопрос также может быть полезным

Ответ 7

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

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, тогда он будет обрабатываться как 32bit.

Ответ 8

Поскольку нам требуется только перевернуть минимальные биты, необходимые для целого числа (например, 50 - 110010, а при инвертировании - 001101, что равно 13), мы можем инвертировать отдельные биты по одному от младшего бита до MSB и смещайте биты вправо и, соответственно, применяйте мощность 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;
        }

Ответ 9

import java.math.BigInteger;
import java.util.Scanner;

public class CodeRace1 {

    public static void main(String[] s) {
        long input;
        BigInteger num,bits = new BigInteger("4294967295");
        Scanner sc = new Scanner(System.in);
        input = sc.nextInt();
        sc.nextLine();
        while (input-- > 0) {
            num = new BigInteger(sc.nextLine().trim());
            System.out.println(num.xor(bits));
        }
    }
}

Ответ 10

Реализация из openJDK, Integer.reverse():

public static int More ...reverse(int i) {
    i = (i & 0x55555555) << 1 | (i >>> 1) & 0x55555555;
    i = (i & 0x33333333) << 2 | (i >>> 2) & 0x33333333;
    i = (i & 0x0f0f0f0f) << 4 | (i >>> 4) & 0x0f0f0f0f;
    i = (i << 24) | ((i & 0xff00) << 8) |
        ((i >>> 8) & 0xff00) | (i >>> 24);
    return i;
}

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

public static int reverse2(int i) {
    i = (i & 0x55555555) << 1 | (i >>> 1) & 0x55555555;
    i = (i & 0x33333333) << 2 | (i >>> 2) & 0x33333333;
    i = (i & 0x0f0f0f0f) << 4 | (i >>> 4) & 0x0f0f0f0f;
    i = (i & 0x00ff00ff) << 8 | (i >>> 8) & 0x00ff00ff;
    i = (i & 0x0000ffff) << 16 | (i >>> 16) & 0x0000ffff;

    return i;
}

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

Ответ 11

Если вы просто хотите перевернуть биты, которые "используются" в целых числах, попробуйте следующее:

public int flipBits(int n) {
    int mask = (Integer.highestOneBit(n) << 1) - 1;
    return n ^ mask;
}

Ответ 12

public static int findComplement(int num) {
    return (~num & (Integer.highestOneBit(num) - 1));
}

Ответ 13

Простой код для реализации перевернутых битов:

#include<stdio.h>

main() {
    unsigned x = 5;
    printf("%u",~x);
}