4 Câu hỏi: làm cho hai bit bằng nhau

câu hỏi được tạo ra tại Wed, May 8, 2019 12:00 AM

Tôi đã trải qua thử thách mã hóa khi tình cờ gặp một câu hỏi để tìm ra số bit thay đổi hoặc cụ thể

  

Đếm số lượng bit được lật để chuyển đổi A thành B

Bây giờ, đối với trường W3C, tôi phát hiện ra rằng chúng ta có thể thực hiện thao tác 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)

Điều tôi nghĩ ban đầu là khi tôi có bit cho cả hai, tôi có thể chạy một vòng lặp for để xem các bit được thay đổi

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

Vì vậy, dựa trên điều này, tôi có hai câu hỏi

  1. Làm cách nào tôi có thể tạo console.log(xorOfAandBToBits) bằng console.log(num1ToBits)

  2. Thay thế tốt hơn để đạt được nhiệm vụ

1
4 Câu trả lời                              4                         

Bạn chỉ cần kiểm tra thời tiết một bit nhất định được đặt trong mảng (bạn cũng có thể chỉ cần lấy chuỗi, không cần phải phân tách):

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

Nếu xor trả về, ví dụ: "1101", điều đó có nghĩa là 3 bit khác nhau, vì vậy bạn thực sự phải đếm số lượng bit được đặt.

Hoặc tôi sẽ làm:

 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

Biểu diễn nhị phân của XOR giữa hai số sẽ có các bit bằng 1 trong đó cả hai đều có các bit riêng biệt. Ví dụ:

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

Vì vậy, để Đếm số bit được lật để chuyển đổi num1 thành num2 , bạn sẽ cần đếm số bit trong 1 cho num1 XOR num2.

Một giải pháp cho vấn đề này có thể dựa trên Brian Kernighan’s Algorithm (, Reference2 )

  

Phép trừ 1 từ một số bật tất cả các bit (từ phải sang trái) cho đến bit được đặt ngoài cùng bên phải (bao gồm cả bit được đặt ngoài cùng bên phải). Vì vậy, nếu chúng tôi trừ đi một số bằng 1 và thực hiện theo bitwise & với chính (n & (n-1)), chúng tôi bỏ đặt bit được đặt ở bên phải. Nếu chúng ta thực hiện n & (n-1) trong loop và đếm số lần loop thực hiện, chúng ta sẽ có được số bit thiết lập. Cái hay của giải pháp này là số lần lặp của nó bằng số bit được đặt trong một số nguyên đã cho.

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

Thực hiện:

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

Thậm chí, bạn có thể thay thế while bằng vòng lặp for như vòng tiếp theo, nhưng không quá dễ đọc:

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

1: Sử dụng

2: Khớp số lượng 1 trong chuỗi bit XOR:

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

/1/g biểu thức chính quy có nghĩa là khớp tất cả 1 trong chuỗi, g là cờ khớp toàn cục, để trả về tất cả các kết quả thay vì chỉ 1.

|| [] đảm bảo 0 được trả về nếu các số giống nhau.

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. Tôi rất đánh giá cao câu trả lời của bạn, điều này có nghĩa gì (/1/g) Daryll?
    2019-05-08 17: 40: 27Z
  2. @ anny123 bài đăng đã chỉnh sửa
    2019-05-08 18: 06: 41Z
nguồn đặt đây