Мне нужно перевернуть все биты в двоичном представлении целого числа. Дано:
10101
Выход должен быть
01010
Что такое побитовый оператор для выполнения этого при использовании с целым числом? Например, если бы я писал метод, подобный int flipBits(int n);, что бы было в теле? Мне нужно перевернуть только то, что уже присутствует в числе, а не все 32 бита в целые числа.
Унарный оператор ~ - побитовое отрицание. Если вам нужно меньше бит, чем то, что подходит в int, тогда вам нужно будет замаскировать его с помощью & после факта.
Просто используйте побитовый оператор ~.
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;
}
Существует несколько способов перевернуть весь бит с помощью операций
x = ~x; // has been mentioned and the most obvious solution.
x = -x - 1; or x = -1 * (x + 1);
x ^= -1; or x = x ^ ~0;
Хорошо, так как до сих пор существует только одно решение, которое дает "правильный" результат, и это... действительно не очень хорошее решение (используя строку для подсчета ведущих нулей, которая будет преследовать меня в моих мечтах;))
Итак, вот мы идем с хорошим чистым решением, которое должно работать - не проверили его, хотя, но вы получите суть. Действительно, 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;
}
быстрее и проще:
/* 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;
}
Мне нужно будет увидеть некоторые примеры, но вы можете получать неожиданные значения из-за двух арифметических дополнений. Если число имеет ведущие нули (как в случае 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 на этот вопрос также может быть полезным
У меня есть другой способ решить этот случай,
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.
Поскольку нам требуется только перевернуть минимальные биты, необходимые для целого числа (например, 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;
}
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));
}
}
}
Реализация из 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 интерпретируется в машинный код...
Если вы просто хотите перевернуть биты, которые "используются" в целых числах, попробуйте следующее:
public int flipBits(int n) {
int mask = (Integer.highestOneBit(n) << 1) - 1;
return n ^ mask;
}
public static int findComplement(int num) {
return (~num & (Integer.highestOneBit(num) - 1));
}
Простой код для реализации перевернутых битов:
#include<stdio.h>
main() {
unsigned x = 5;
printf("%u",~x);
}