ต้องพลิกขั้นต่ำเพื่อเพิ่มจำนวนด้วย k set bits ใน C++

คำชี้แจงปัญหา

จากสองตัวเลข n และ k เราจำเป็นต้องค้นหาจำนวนการพลิกขั้นต่ำที่จำเป็นในการเพิ่มจำนวนที่กำหนดให้มากที่สุดโดยการพลิกบิตเพื่อให้จำนวนผลลัพธ์มี k ชุดบิตพอดี โปรดทราบว่าการป้อนข้อมูลจะต้องเป็นไปตามเงื่อนไขที่ k <จำนวนบิตใน n.

ตัวอย่าง

สมมุติว่า n =9 และ k =2
การแทนค่าไบนารีของ 9 คือ − 1001 ประกอบด้วย 4 บิต
เลขฐานสอง 4 หลักที่ใหญ่ที่สุดที่มี 2 ชุดบิตคือ - 1100 เช่น 12
ในการแปลง 1001 เป็น 1100 เราต้องพลิกไฮไลต์ 2 บิต

อัลกอริทึม

<ก่อน>1. นับจำนวนบิตใน n ให้เราเรียกตัวแปรนี้ว่า bitCount เราสามารถใช้ฟังก์ชัน log2(n) จากไลบรารีคณิตศาสตร์เป็น fllows:bitCount =log2(n) + 1;2 ค้นหาจำนวนที่มากที่สุดด้วย k ชุดบิตดังนี้ maxNum =pow(2, k) - 1;3 ค้นหาจำนวนที่มากที่สุดที่เป็นไปได้ด้วยชุดบิต k และมีจำนวนบิตเท่ากันทุกประการดังนี้:maxNum =maxNum <<(bitCount - k);4. คำนวณ (n ^ maxNum) และนับจำนวนชุดบิต

ตัวอย่าง

#include #include ใช้เนมสเปซ std;int getSetBits(int n){ int cnt =0; ในขณะที่ (n) { ++cnt; n =n &(n - 1); } return cnt;}int minFlipsRequired(int n, int k){ int bitCount, maxNum, flipCount; bitCount =log2(n) + 1; maxNum =pow(2, k) - 1; maxNum =maxNum <<(bitCount - k); flipCount =n ^ maxNum; return getSetBits(flipCount);}int main(){ cout <<"การพลิกขั้นต่ำที่จำเป็น:" < ผลลัพธ์
 
 เมื่อคุณคอมไพล์และรันโปรแกรมข้างต้น มันสร้างผลลัพธ์ต่อไปนี้ -
 พลิกขั้นต่ำที่ต้องการ:2