Cách tốt nhất để lặp qua các số nguyên với tối đa k bit ON là gì?

Question

Tôi cần lặp qua tất cả các số nguyên n bit có nhiều bít bit k nhất (bit 1), trong đó 0 < n < = 32 và 0 < = k < = n. Ví dụ, nếu n = 4 và k = 2 thì các số này là (theo số nhị phân): 0000, 0001, 0010, 0100, 1000, 0011, 0101, 0110, 1001, 1010, 1100. Thứ tự các số này looped thông qua là không quan trọng, nhưng mỗi được truy cập chỉ một lần.

Hiện nay tôi đang sử dụng thuật toán đơn giản này:

for x = 0 to (2^n - 1) 
    count number of bits 1 in x 
    if count <= k 
     do something with x 
    end if 
end for 

Tôi nghĩ rằng thuật toán này là không hiệu quả bởi vì nó có để lặp qua quá nhiều con số. Ví dụ, nếu n = 32 và k = 2 thì nó phải lặp qua 2^32 số để chỉ tìm thấy 529 số (có < = 2 bit 1).

Câu hỏi của tôi là: có bất kỳ thuật toán hiệu quả hơn nào để thực hiện việc này không?

Answer 1

Bạn sẽ cần phải thực hiện thuật toán đếm bit của riêng bạn để tăng bộ đếm vòng lặp. Về cơ bản, để tính số tiếp theo trong chuỗi, nếu có ít hơn k '1' bit, tăng bình thường, nếu có k '1' bit, giả vờ bit '0' sau ít nhất có ý nghĩa '1' không tồn tại và tăng bình thường.

Một cách khác để nói rằng với bộ đếm chuẩn bạn thêm 1 vào bit ít quan trọng nhất và mang theo. Trong trường hợp của bạn, khi có k số '1's bạn sẽ thêm vào 1 đến bit' 1 'thấp nhất.

Ví dụ nếu k là 2 và bạn có 1010 bỏ qua cuối cùng 0 và thặng dư 101 để bạn có được 110 và sau đó thêm vào 0 cho 1100.

Đây là Mã giả cho incrementing số:

Count 1 bits in current number 
If number of 1's is < k 
    number = number + 1 
Else 
    shift_number = number of 0 bits after least significant 1 bit 
    number = number >> shift_number 
    number = number + 1 
    number = number << shift_number 

Answer 2

Nếu bạn phải thiết lập 2 bit trong 4 bit thiết lập thấp nhất phải có ít nhất ba (tính từ 0 ... 3) và cao nhất ít nhất là giây.

Vì vậy, bạn có thể lặp với 2 vòng

for lowest in 0 to (n-k) 
    for highest in lowest + 1 to 3 
    (0000).setBit (lowest).setBit (highest) 

Vì bạn không muốn viết 16 vòng cho 16 bit, bạn có thể chuyển đổi ý tưởng này thành một trong những đệ quy.

Answer 3

bạn có thể sử dụng vòng lặp while như được hiển thị bên dưới. Vòng lặp này sẽ chỉ lặp lại không có bit trên. Trong trường hợp của bạn không có các bit là cố định, bạn có thể sử dụng một break

countbits = 0 
while num > 0 
    num = num & (num-1) 
    countbits = countbits + 1 
end while 

ví dụ:
nếu 64 (1000000) nó sẽ lặp chỉ một lần,
nếu 72 (1.001.000) sau đó 2 lần

Answer 4

tổ hợp.

Nếu bạn có số nguyên có độ dài n bit và r bit được đặt thì có nCr số đó. Chỉ cần sử dụng trình tạo kết hợp và lặp qua các kết hợp phù hợp.

Answer 5

Lấy câu trả lời cho Bit hack to generate all integers with a given number of 1s và lặp lại trên [1,k].Điều đó sẽ tạo ra mỗi số nguyên với tối đa k bit một lần.