时间戳

首页 > 解决方案 > 查找具有最大/最小位数集的数字

c - 查找具有最大/最小位数集的数字

问题描述

给定一个整数范围，我如何找到该范围内设置最大和最低位数的数字？

例如，给定范围[32, 65]，63 具有最大数量的比特集（即六，因为二进制表示是111111），32 和 64 具有最低数量（即，一，因为二进制表示是100000and 1000000）。

对于非常大的数字/范围（2 ^ 50），必须快速工作。

标签： calgorithmbit-manipulation

解决方案

尝试找到范围内的 2 的最高幂。这可以通过在循环中取上界并将其与自身减去 1 进行与运算来完成，例如：

temp = upper_bound;
while( (temp & (temp-1)) != 0) {
    temp = temp & (temp-1);
}

if(temp < lower_bound) {
    // No power of 2 found within range
}

如果上一步没有找到范围内的2的幂；您会发现 2 的幂不在范围内。清除上下界对应位并递归；喜欢：

void find_bits(unsigned int lower_bound, unsigned int upper_bound, unsigned int extra_bits) {
    unsigned int temp = upper_bound;
    while( (temp & (temp-1)) != 0) {
        temp = temp & (temp-1);
    }

    if(temp < lower_bound) {
        find_bits(lower_bound ^ temp, upper_bound ^ temp, extra_bits + 1);
        return;
    }

如果零在该范围内，则设置位的最小数量为零（从数字零开始）。否则，设置位的最小数量为 1（范围内的任何 2 的幂，包括您找到的 2 的最高幂）。不要忘记考虑以前清除的任何额外位：

    if(lower_bound == 0) {
        least_set_bits = 0 + extra_bits;
    } else {
        least_set_bits = 1 + extra_bits;
    }

如果范围负 1 内 2 的最高幂也在该范围内，则设置位的最大数量将是范围负 1 内 2 的最高幂的数量。否则，上限必须与下界，因此最大数量的设置比特等于最小数量的设置比特：

    if(temp - 1 < lower_bound) {
        most_set_bits = least_set_bits;
    } else {
        temp--;
        most_set_bits = 0;
        while(temp > 0) {
            temp >>= 1;
            most_set_bits++;
        }
        most_set_bits += extra_bits;
    }

以上所有内容（未经测试且可能存在错误；并且绝对无法处理某些极端情况 - 例如，如果范围为 [0, 0]）：

void find_bits(unsigned int lower_bound, unsigned int upper_bound, unsigned int extra_bits) {
    unsigned int temp = upper_bound;
    unsigned int least_set_bits;
    unsigned int most_set_bits;

    while( (temp & (temp-1)) != 0) {
        temp = temp & (temp-1);
    }

    if(temp < lower_bound) {
        find_bits(lower_bound ^ temp, upper_bound ^ temp, extra_bits + 1);
        return;
    }

    if(lower_bound == 0) {
        least_set_bits = 0 + extra_bits;
    } else {
        least_set_bits = 1 + extra_bits;
    }

    if(temp - 1 < lower_bound) {
        most_set_bits = least_set_bits;
    } else {
        temp--;
        most_set_bits = 0;
        while(temp > 0) {
            temp >>= 1;
            most_set_bits++;
        }
        most_set_bits += extra_bits;
    }

    printf("Least set bits is %u, most set bits is %u.\n", least_set_bits, most_set_bits);
}

推荐阅读