剑指offer——面试题10输入一个十进制整数,统计其中二进制1的个数

/**
 * 题目:输入一个十进制整数,统计其中二进制1的个数
 * @author 大闲人柴毛毛
 */
public class CountBitOne {
	/**
	 * 这个问题最直观的思路:
	 * 将输入的整数转换成二进制数,
	 * 再把这个二进制数转换成字符数组,
	 * 最后遍历数组,统计1的个数。
	 * 
	 * 使用数组需要开辟额外的内存空间,
	 * 若在不能使用Java相关类库的情况下,
	 * 要实现十进制向二进制数组的转化实属不易。
	 * 且该方法需要完整遍历数组,因此需要n次比较。
	 * 
	 * 下面我们探求更高效的方法。
	 */
	
	
	/**
	 * 这道题涉及到二进制,因此我们应当敏锐地察觉到使用位运算来解决问题!
	 * 
	 * 位运算具有如下特性:
	 * 1与一个二进制数进行与运算,若最低位是1,则运算的结果为1,否则结果为0。
	 * 
	 * 因此,让输入的数与1进行与运算,每运算一次便统计当前结果是否为1,并将数右移一位,
	 * 当该数为0时统计结束。
	 * 
	 * 代码实现如下:
	 */
	public static int countBitOne_1(int n){
		//n中1的个数
		int count = 0;
		while(n!=0){
			//判断当前运算结果是否为1
			if((n&1)==1)
				count++;
			//将n右移一位
			n = n >> 1;
		}
		return count;
	}
	
	
	
	/**
	 * 上述方法有个严重的bug!
	 * 若一个正数右移n位,则需要用n个1来补齐最高位。
	 * 因此,当一个正数右移了若干次之后,它的所有位置都被1取代,
	 * 此时与1进行与运算的结果永远是1,从而出现了死循环。
	 * 
	 * 如何解决呢?
	 * 
	 * 出现上述情况的原因有两个:1.右移、2.正数,
	 * 只要破坏了这两个条件中的任何一个,就能避免死循环的现象。
	 * 由于本题的输入要求中包含了正整数,因此我们只能破坏第一个条件。
	 * 
	 * 虽然右移与正负有关,但左移与正负无关!
	 * 并且要达到和方法1一样的效果,我们就让“00000001”这个序列左移。
	 * 
	 * 代码如下:
	 */
	public static int countBitOne_2(int n){
		//n中1的个数
		int count = 0;
		//进行左移的序列00000001
		int flag = 1;
		//当flag不为0的时候循环
		while(flag!=0){
			//若当前与运算结果不为0,则表示n当前位置是1
			if((n&flag) != 0)
				count++;
			//flag左移一位
			flag = flag << 1;
		}
		return count;
	}
	/**
	 * 这种方式不需要额外的内存空间,
	 * 而且十进制位运算的过程中,进制的转化由JVM完成,无需程序猿手动实现。
	 * 这种方法的时间复杂度为O(n),需要进行n次比较。
	 * 
	 * 下面介绍更高效的方式。
	 */
	
	
	
	/**
	 * 如果将一个二进制数-1,那么该二进制数最右侧的1将会变成0,1后面的0均变成1,1前面的数保持不变。
	 * 也就是说,如果一个二进制数-1,那么该数最右侧的1及1右侧的所有数均变成相反数。
	 * 如果把这个数和原数与运算,那么最右侧的那个1前面的数将不变,1及1右侧的所有数均变为0。
	 * 也就是说,进行一次上述的运算后,原数最右侧的那个1将会变成0,
	 * 那么只要重复上述操作,当原数变成0时,循环的次数就是1的个数。
	 * 
	 * 代码如下:
	 */
	public static int countBitOne_3(int n){
		//n中1的个数
		int count = 0;
		while(n!=0){
			n = n & (n-1);
			count++;
		}
		return count;
	}
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏C/C++基础

2018腾讯内部调岗面试试题1——使用C/C++但不能用sizeof判断操作系统是32位还是64位

2018上半年折腾了一回,想换个后台开发岗尝试锻炼一下自己,面了三个部门,将有关有意思的题目汇总记录下来,供大家参考。

581
来自专栏java思维导图

MySQL函数及用法示例(收藏大全)

1、字符串函数 ascii(str) 返回字符串str的第一个字符的ascii值(str是空串时返回0) mysql> select ascii('2...

703
来自专栏老九学堂

十七个C语言新手编程时常犯的错误及解决方式

编译程序把a和A认为是两个不同的变量名,而显示出错信息。C认为大写字母和小写字母是两个不同的字符。习惯上,符号常量名用大写,变量名用小写表示,以增加可读性。

1234
来自专栏cloudskyme

memset,memcpy,strcpy 的区别

一.函数原型    strcpy    extern char *strcpy(char *dest,char *src);    #include <stri...

33012
来自专栏HelloCode开发者学习平台

BAT面试算法进阶(2)-两数相加

You are given two non-empty linked lists representing two non-negative integ...

872
来自专栏本立2道生

实例分析C程序运行时的内存结构

这段代码包含两个函数,因此可以测试函数调用,此外还包含了静态变量、局部变量、返回值等

441
来自专栏菜鸟计划

javascript简史

一、javascript简介 1.1 javascript简史 javascript诞生于1995年。当时它的主要目的是处理以前由服务器端语言负责的一些输入验证...

2615
来自专栏向治洪

Kotlin语法基础之控制流

Kotlin 的控制流与 Java 的控制流基本相同,只是使用 when 代替了 switch。当然,在 Kotlin中,if 和 when 不仅仅可以作为语句...

1807
来自专栏WD学习记录

牛客网 和为S的两个数字

输入一个递增排序的数组和一个数字S,在数组中查找两个数,使得他们的和正好是S,如果有多对数字的和等于S,输出两个数的乘积最小的。

894
来自专栏静晴轩

Javascript数组操作

使用JS也算有段时日,然对于数组的使用,总局限于很初级水平,且每每使用总要查下API,或者写个小Demo测试下才算放心,一来二去,浪费不少时间;思虑下,堪能如此...

3778

扫描关注云+社区