4 Вопрос: сделать равными два бита

вопрос создан в Wed, May 8, 2019 12:00 AM

Я столкнулся с проблемой кодирования, когда наткнулся на вопрос, чтобы узнать количество битов, которые изменились или были конкретными

  

Подсчитать количество бит, которое нужно перевернуть, чтобы преобразовать A в B

Теперь для школы W3C я узнал, что мы можем выполнить операцию xor

р>

const num1 = 10 
const num2 = 20 
const xorAandB = num1 ^ num2 //this would give 30 
console.log(xorAandB) 
const xorOfAandBToBits = xorAandB.toString(2) 
console.log(xorOfAandBToBits) //11110 (5 numbers)
const num1ToBits = num1.toString(2)
console.log(num1ToBits) //(4 numbers)

Сначала я подумал, что, когда у меня есть биты для них обоих, я могу запустить цикл for, чтобы увидеть измененные биты

const num1ToBitsArray = num1ToBits.split('') 
const xorBitsNumberToArray = xorOfAandBToBits.split('')
let count = 0
for (let i=0; i<num1ToBitsArray.length; i++) {
if (xorBitsNumberToArray[i] !== num1ToBitsArray[i]) count++ 
}

Итак, исходя из этого, у меня есть два вопроса

  1. Как я могу сделать console.log(xorOfAandBToBits) равным console.log(num1ToBits)

  2. Лучше альтернативы для достижения задачи

1
4 ответа                              4                         

Вам просто нужно проверить, установлен ли определенный бит в массиве (вы также можете просто взять строку, не нужно разбивать):

 if(xorBitsNumberToArray[i] === "1") count++;

Если XOR возвращает, например, «1101», это означает, что 3 бита были разными, поэтому вам нужно посчитать количество установленных битов.

Или я бы сделал:

 const difference = a ^ b;
 let count = 0;

 for(let i = 0; i < 32; i++)
   count += (difference >> i) & 1;
    
1
2019-05-08 15: 50: 47Z

р>

const num1 = 10 
const num2 = 20
function dec2bin(dec){
  return (dec >>> 0).toString(2);
}
const xor = dec2bin(num1 ^ num2);
count=0;
for(let x in xor){
  if(xor[x]=='1'){
    count++;
  }
}
console.log(count)
    
1
2019-05-08 15: 57: 38Z

Двоичное представление XOR между двумя числами будет иметь биты, равные 1, где они оба имеют разные биты. Пример: р>

р>

const num1 = 10;
const num2 = 20;
const xorAandB = num1 ^ num2;
console.log(num1, "->", "0" + num1.toString(2));
console.log(num2, "->", num2.toString(2));
console.log(xorAandB, "->", xorAandB.toString(2));
.as-console {background-color:black !important; color:lime;}
.as-console-wrapper {max-height:100% !important; top:0;}

Итак, чтобы подсчитать количество бит, которое нужно перевернуть, чтобы конвертировать num1 в num2 , вам нужно посчитать количество бит в 1 для num1 XOR num2.

Одно из решений этого может быть основано на Brian Kernighan’s Algorithm ( reference1 , reference2 )

  

Вычитание 1 из числа переключает все биты (справа налево) до самого правого установленного бита (включая самый правый установленный бит). Так что, если мы вычтем число на 1 и сделаем побитовое & с самим (n & (n-1)), мы сбрасываем самый правый установленный бит. Если мы сделаем n & (n-1) в loop и посчитаем, сколько раз выполняется loop, мы получим установленный счетчик битов. Прелесть этого решения состоит в том, что число циклов, которое оно повторяет, равно количеству установленных битов в данном целом числе.

Pseudocode:

1  Initialize count: = 0
2  If integer n is not zero
  (a) Do bitwise & with (n-1) and assign the value back to n -> n := n & (n-1)
  (b) Increment count by 1
  (c) go to step 2
3  Else return count

Реализация:

р>

const bitsToFlip = (num1, num2) =>
{
    let num = num1 ^ num2, count = 0;

    while (num)
    {
        num &= num - 1;
        count++;
    }

    return count;
}

console.log("Bits to flip for (10, 20) =", bitsToFlip(10, 20));
console.log("Bits to flip for (1, 2) =", bitsToFlip(1, 2));
console.log("Bits to flip for (0, 7) =", bitsToFlip(0, 7));
.as-console {background-color:black !important; color:lime;}
.as-console-wrapper {max-height:100% !important; top:0;}

Более того, вы можете заменить while на цикл for, как следующий, но не слишком читаемый:

for (count = 0; num; count++, num &= num - 1);
    
1
2019-05-08 17: 02: 08Z

1: используйте String.padStart ( 5, '0')

2: соответствует числу 1 в битовой строке XOR:

const bitsChanged = (xorBits.match(/1/g) || []).length; р>

/1/g - это регулярное выражение означает совпадение всех 1 в строке, g - глобальный флаг соответствия, чтобы вернуть все совпадения вместо 1.

|| [] гарантирует, что возвращается 0, если числа совпадают.

р>

const num1 = 10, num2 = 20;
const xorNum = num1 ^ num2;
const xorBits = xorNum.toString(2);
const bitsChanged = (xorBits.match(/1/g) || []).length;

console.log(bitsChanged + " bits differ");
    
1
2019-05-08 18: 09: 38Z
  1. Я так ценю ваш ответ, что это значит (/1/g) Дэрилл?
    2019-05-08 17: 40: 27Z
  2. @ anny123 отредактированное сообщение
    2019-05-08 18: 06: 41Z
источник размещен Вот