非移位解法--java
二进制中1的个数
http://www.nowcoder.com/questionTerminal/8ee967e43c2c4ec193b040ea7fbb10b8
前边看了好多都是直接利用负数在计算机中直接是以补码形式存在来进行解题的,为了加深记忆,我从头到尾利用两个栈模拟队列编写了一下,有更好想法的一起讨论。
(为了提高空间利用率,使用一个List应该是完全可以的,我懒得写了。。。。)
import java.util.Stack; import java.util.ArrayList; public class Solution { public int NumberOf1(int n) { Stack<Integer> number=new Stack<>(); //用来存放原码和反码 Stack<Integer> number2=new Stack<>(); //存放补码 ArrayList<Integer> numTemp=new ArrayList<>(); //用来临时存放,从而达到顺序不变的情况下和前边的空位进栈 int num=0; int numAll=0; if(n>0){ while(n!=0){ number.push(n%2); n=n/2; } while(!number.isEmpty()){ if(number.pop()==1){ num++; } } return num; } else if(n<0){ int absNumber=Math.abs(n); while(absNumber!=0){ numTemp.add(absNumber%2==1?0:1); absNumber=absNumber/2; } for(int i=0;i<(31-numTemp.size());i++){ number.push(1); } for (int i = numTemp.size()-1; i >=0; i--) { number.add((Integer)numTemp.get(i)); } numTemp.clear(); int supplement=1; while(!number.isEmpty()){ if(number.pop()+1==2){ number2.push(0); }else{ number2.push(1); break; } } while(!number.isEmpty()){ number2.push(number.pop()); } while(!number2.isEmpty()){ if(number2.pop()==1){ num++; } } return num+1; } return 0; } }