Count 1 in Binary
Count how many 1 in binary representation of a 32-bit integer.
Example
Given 32, return 1
Given 5, return 2
Given 1023, return 9
Challenge
If the integer is n bits with m 1 bits. Can you do it in O(m) time?
思路:
记住这个trick:每次n & (n – 1),会把n去掉一个1。
例子:
1111 & 1110 = 1110 (4 -> 3)
1110 & 1101 = 1100 (3 -> 2)
If the integer is n bits with m 1 bits. Can you do it in O(m) time?
思路:
记住这个trick:每次n & (n – 1),会把n去掉一个1。
例子:
1111 & 1110 = 1110 (4 -> 3)
1110 & 1101 = 1100 (3 -> 2)
public class Solution { /** * @param num: an integer * @return: an integer, the number of ones in num */ public int countOnes(int num) { // write your code here int count = 0; while (num != 0) { num = num & (num - 1); count++; } return count; } }