返回不重复的整数

指定整数位数,返回不重复的整数,其实就是全排列的问题

每一位要么是0要么是1,所以如果需要求n位的全排列,所有可能的情况总数为2^n

实际应用,比如我们需要扫描全球ipv4的80端口,统计有多少80端口是开放的,但是我们又想随机去扫,避免被特定策略检测到,其实就是求32位的随机全排列

linux c例子

#include <stdio.h>
#include <time.h>
#include <stdlib.h>

unsigned int sum;

void permute(unsigned int n, int len) 
{
    unsigned int i,t;

    if (len == 0) {
        sum++;
        printf("%u ", n);
        return;
    }

    i = rand() % 2;
    
    permute((n << 1) | i, len-1);
    
    if(i)
        i = 0;
    else
        i = 1;

    permute((n << 1) | i, len-1);

}

int main(int argc, char **argv) 
{
    if (argc != 2) {
        printf("./a.out bit_long\n");
        return 1;
    }

    srand((unsigned)time(NULL));

    int bit_long = atoi(argv[1]);
    unsigned int n = 0;
    permute(n, bit_long);

    printf("\n\nsum:%d\n", sum);

    return 0; 
}
[root@dldl ccc]# ./a.out 4
14 15 13 12 11 10 9 8 0 1 2 3 6 7 4 5 

sum:16
[root@dldl ccc]# ./a.out 5
11 10 9 8 13 12 14 15 5 4 7 6 1 0 2 3 30 31 28 29 27 26 25 24 20 21 22 23 18 19 17 16 

sum:32
[root@dldl ccc]# ./a.out 6
5 4 6 7 0 1 3 2 13 12 15 14 10 11 8 9 18 19 16 17 20 21 23 22 27 26 24 25 28 29 30 31 46 47 45 44 42 43 41 40 34 35 33 32 37 36 38 39 54 55 53 52 51 50 49 48 60 61 62 63 56 57 58 59 

sum:64

为了让排列能真的随机,上面的随机取值部分可以优化

上一篇: 位图-布隆过滤器
下一篇: 哈希算法
作者邮箱: 203328517@qq.com