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

Question

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

10101

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

01010

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

Answer 1

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

Answer 2

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

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

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

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

    return ~n & mask;
}

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

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

Answer 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;

Answer 4

более быстрое и простое решение:

/* 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;
}

Answer 5

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

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

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;
}

Answer 6

Вы можете попробовать это:

/**
 * Flipping bits of a decimal Integer.
 */
public class FlipBits {

    public static final char ONE_CHAR = '1';
    public static final char ZERO_CHAR = '0';

    static int flipBits(int n) {
        String nBinary = Integer.toBinaryString(n);
        System.out.println("Original number is decimal " + n + ", and binary  " + nBinary);
        char[] result = new char[nBinary.length()];
        char[] nBinaryChars = nBinary.toCharArray();
        for (int i = 0; i < nBinaryChars.length; i++) {
            result[i] = nBinaryChars[i] == ONE_CHAR ? ZERO_CHAR : ONE_CHAR;
        }
        int resultDecimal = Integer.parseInt(String.valueOf(result), 2);
        System.out.println("Flipped number in decimal is " + resultDecimal
                + ", and in binary is " + String.valueOf(result));
        return resultDecimal;
    }

    public static void main(String[] args) {
        int input = 21;
        int flippedInteger = flipBits(input);
        System.out.println(input + " becomes " + flippedInteger + " after flipping the bits.");
    }

}

Пример вывода:

Исходное число десятичное 21, и двоичное 10101
Число перевёрнутых в десятичном виде 10, а в двоичном виде 01010
21 становится 10 после переключения битов.

Answer 7

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

Answer 8

Если вы просто хотите перевернуть биты, которые «используются» в целом числе, попробуйте это:

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

Answer 9

Реализация из 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-код интерпретируется в машинный код ...

Answer 10

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));
        }
    }
}