Source
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?
题解
题 O1 Check Power of 2 的进阶版，x & (x - 1) 的含义为去掉二进制数中最后一的1，无论 x 是正数还是负数都成立。
Java
public class Solution { /** * @param num: an integer * @return: an integer, the number of ones in num */ public int countOnes(int num) { int count = 0; while (num != 0) { num = num & (num - 1); count++; } return count; } }
源码分析
累加计数器即可。
复杂度分析
这种算法依赖于数中1的个数，时间复杂度为 O(m). 空间复杂度 O(1).
原创文章，作者：奋斗，如若转载，请注明出处：https://blog.ytso.com/tech/pnotes/20709.html