`
seya
  • 浏览: 359892 次
  • 性别: Icon_minigender_1
  • 来自: 南京
社区版块
存档分类
最新评论

求bit位中1的总个数为n的所有整数集合

 
阅读更多
public class TTT {
	public static void main(String[] args) {
		int[] array = new int[31];
		new TTT().arrange(array, array.length, 3, 0);
	}
	
	public void arrange(int[] array, int left, int mNum, int start) {
		if (mNum == 0) {
			for (int i = 0; i < array.length; i++) {
				System.out.print(array[i]);
			}
			System.out.print("====");
			//print the value
			int sum = 0;
			for (int i = 0; i < array.length; i++) {
				if (array[i] == 1) {
					sum += 1 << i;
				}
			}
			System.out.println(sum);
		} else if (mNum == left) {
			for (int i = 0; i < array.length; i++) {
				if (array.length - i <= mNum) {
					array[i] = 1;
				}
				System.out.print(array[i]);
			}
			System.out.print("====");
			//print the value
			int sum = 0;
			for (int i = 0; i < array.length; i++) {
				if (array[i] == 1) {
					sum += 2 << i;
				}
			}
			System.out.println(sum);
		}  else {
			
			//assign 0, reset bits after start to 0.
			/*for (int i = 0; i < array.length && i >= start; i++) {
				array[i] = 0;
			}*/
			array[start] = 0;
			arrange(array, left - 1, mNum, start + 1);
			
			
			//clean array for next search
			for (int i = 0; i < array.length; i++) {
				if (i >= start) {
					array[i] = 0;
				}
			}
			
			//assign 1
			array[start] = 1;
			arrange(array, left - 1, mNum-1, start + 1);
		}
	}
}

分享到:
评论

相关推荐

    A Collection of Bit Programming Interview Questions solved in C++.pdf

    给定一个只有一个位被设置为1的无符号整数,找到该位的位置。 **解决方案概述:** 可以使用循环右移和按位与运算来确定被设置的位的位置。 **代码示例:** ```cpp int find_set_bit_position(unsigned int n) { ...

    集合运算 求并集和交集

    2. 位向量:如果集合元素范围较小且为整数,可以用位向量表示集合。每个元素对应位向量的一位,通过按位或(求并集)和按位与(求交集)操作,快速得出结果。位运算的时间复杂度极低,一般为O(1)。 总结来说,顺序...

    世界500强面试题.pdf

    1.5.6. 输入两个整数 n 和 m,从数列 1,2,3.......n 中 随意取几个数 ....... 116 1.5.7. 输入一个表示整数的字符串,把该字符串转换成整数并输出.............. 118 1.5.8. 给出一个数列,找出其中最长的单调...

    数字的表示

    更一般地,对于一个n+1位的十进制数,其表示为: \[(a_na_{n-1}a_1a_0) = a_n \times 10^n + \cdots + a_1 \times 10^1 + a_0 \times 10^0\] 其中\(a_k\)是自然数,且满足\(0 \leq a_k )。这里,10作为基数可以被...

    大数据量,海量数据-处理方法总结

    还可以使用 Spectral Bloom Filter 将集合中的元素映射到位数组中,用 k(k 为哈希函数个数)个映射位是否全 1 表示元素在不在这个集合中。 在实践中,需要根据输入元素个数 n,确定位数组 m 的大小及 Hash 函数个...

    c语言位运算.pdf

    4. **按位取反(~)**: 这是一个一元运算符,它会反转输入数的所有二进制位,将0变为1,1变为0。通常用于创建位掩码。 - 示例: ```c int a = 10; // 00001010(2) int result = ~a; // 11110101(2) -&gt; -11(在有...

    关于《数》的分类及介绍

    - **整数**:整数集合包括了所有正整数、负整数以及零。整数是人类最早掌握的数学工具之一,是进行基本数学运算的基础。 - **正整数**:1、2、3…… - **负整数**:-1、-2、-3…… - **零**:0 #### 双整数 - *...

    面试中的大数据处理

    其基本原理是使用位数组+k个独立的hash函数,将hash函数对应的值的位数组置1,查找时如果发现所有hash函数对应位都是1,说明存在。Bloom filter有两个重要的问题:如何根据输入元素个数n确定位数组m的大小及hash函数...

    常用大数据量,海量数据处理方法,算法总结

    其原理是使用位数组+k 个独立的哈希函数,将哈希函数对应的值的位数组置 1,查找时如果发现所有哈希函数对应位都是 1 则说明存在。Bloom filter 可以用来解决大数据量的问题,但它并不保证查找结果的正确性,并且不...

    自然数最优分解乘积最大的严格数学证明.pdf

    在解决这个问题时,我们需要考虑将一个正整数n分解为不同的自然数之和,并希望这些自然数的乘积达到最大。 为了实现这一目标,本文提出了一种“最优分解”策略。所谓的“最优分解”指的是,通过数学证明和算法描述...

    NAND Flash ECC算法研究

    相应地,二进制 BCH 码以 α,α3,α5,…, α2t-1 为根,码长 n=LCM(φ1,φ3,…,φ1t-1),码的校验矩阵就为其中 φ1,φ3,…,φ2t-1 分别是 α,α3,α5,…, α2t-1 对应元素的级,所以二进制 BCH 码的码长是 n≤2m...

    大数据量,海量数据处理方法总结[参考].pdf

    查询时,如果所有哈希函数对应位均为1,则可能存在于集合中,但可能存在误报(False Positive)。Bloom Filter不支持删除操作,但Counting Bloom Filter通过使用计数器数组代替位数组,解决了这个问题。为了确定位数...

    表求交论文集

    5. **位运算**:对于较小的整数集合,可以利用位运算技巧,如位向量(Bit Vector),通过按位与(AND)操作快速找到交集,这种方法在内存有限的嵌入式系统中特别有用。 6. **分布式计算**:随着大数据时代的到来,...

    海量数据处理总结(大量数据处理)

    - **案例三:整数去重**:在2.5亿个整数中找出不重复的整数个数,当内存不足以容纳所有数据时,可以采用Bit-Map或优化后的Bloom Filter来标记元素的出现情况,进而统计不重复整数的数量。 ### 结论 海量数据处理...

    大数据量,海量数据 处理方法总结

    4. **整数去重计数**:在2.5亿个整数中找出不重复的整数个数,当内存不足以存储全部整数时,可通过Bit-Map或Bloom Filter来估算不同整数的数量,利用其空间高效性解决。 通过上述方法的总结与实践案例的解析,我们...

    经典面试题——海量数据库

    - **URL交集问题**:对于两个大型文件的URL交集,可以使用Bloom Filter或Bit-Map来判重,先将一个文件的所有URL加入数据结构,再扫描另一个文件并检查是否存在于数据结构中。 - **访问IP统计**:面对海量日志数据...

Global site tag (gtag.js) - Google Analytics