|
| 1 | +packageeasy; |
| 2 | +/**191. Number of 1 Bits QuestionEditorial Solution My Submissions |
| 3 | +Total Accepted: 105389 |
| 4 | +Total Submissions: 279235 |
| 5 | +Difficulty: Easy |
| 6 | +Write a function that takes an unsigned integer and returns the number of ’1' bits it has (also known as the Hamming weight). |
| 7 | +
|
| 8 | +For example, the 32-bit integer ’11' has binary representation 00000000000000000000000000001011, so the function should return 3.*/ |
| 9 | +publicclassNumberOfIBits { |
| 10 | +// you need to treat n as an unsigned value |
| 11 | +publicinthammingWeight(intn) { |
| 12 | +//cheers! Made it AC'ed on my own with an ease! |
| 13 | +intcount =0; |
| 14 | +for(inti =0;i <32;i++){ |
| 15 | +intone = (n >>>i) &1;//must use unsigned right shift operator |
| 16 | +if(one ==1)count++; |
| 17 | + } |
| 18 | +returncount; |
| 19 | + } |
| 20 | + |
| 21 | +//then I turned to its Editorial solution: we can make it a little faster: at any time, when n becomes zero, that means there's |
| 22 | +//no more 1's there, then we could safely return! Cool! |
| 23 | +publicinthammingWeight_faster(intn) { |
| 24 | +intcount =0; |
| 25 | +for(inti =0;i <32;i++){ |
| 26 | +intone = (n >>>i) &1;//must use unsigned right shift operator |
| 27 | +if(one ==1)count++; |
| 28 | +if(n ==0)returncount; |
| 29 | + } |
| 30 | +returncount; |
| 31 | + } |
| 32 | + |
| 33 | +//another cool trick that I learned: doing bitwise AND operation between n and n-1 will always flip the least significant 1 bit in n |
| 34 | +//to zero, here's the solution from Editorial: |
| 35 | +publicinthammingWeight_editorial(intn){ |
| 36 | +intcount =0; |
| 37 | +while(n !=0){ |
| 38 | +count++; |
| 39 | +n &= (n-1); |
| 40 | + } |
| 41 | +returncount; |
| 42 | + } |
| 43 | +//example run for the above editorial solution: input 5, n will be 5&4 and becomes 4, then in the next run, n will become 4&3 which is 0, thus exit the while loop. |
| 44 | + |
| 45 | + |
| 46 | +publicstaticvoidmain(String...strings){ |
| 47 | +System.out.println(4&5); |
| 48 | +NumberOfIBitstest =newNumberOfIBits(); |
| 49 | +System.out.println(test.hammingWeight_editorial(5)); |
| 50 | + } |
| 51 | +} |