[LintCode] Count 1 in Binary [典型位运算题目]

ZHAO_ 发布于2019-08-14 15:16 / 319人阅读

摘要：这道题，给我解决了两个疑问，还剩一个。首先是要用无符号右移运算符，其次是可以用一个不断左移的二进制作为参照。

Problem

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 bits. Can you do it in O(m) time?

Note

这道题，Olivia给我解决了两个疑问，还剩一个。首先是要用无符号右移运算符>>>，其次是可以用一个不断左移的二进制1作为参照。那么如何获得一个用1来进行补位的左移的1呢？
第一种解法，num右移，每次对末位进行比较，直到num为0；
第二种解法，1左移，每次和num的第i位比较，直到i = 32；
第三种解法，num和num-1逐位与，去1，直到num为0。

Solution

public class Solution {
    public int countOnes(int num) {
        int count = 0;
        while (num != 0) {
            count += (num & 1);
            num >>>= 1;
        }
        return count;
    }
};

public class Solution {
    public int countOnes(int num) {
        int count = 0;
        for(int i = 0 ; i < 32; i++) {
            if((num & (1<
3.
public class Solution {
    public int countOnes(int num) {
        int count = 0;
        while (num != 0) {
            num &= num - 1;
            count++;
        }
        return count;
    }
}
// 1111    1110    1110
// 1110    1101    1100
// 1100    1011    1000
// 1000    0111    0000

服务器托管海外云主机 in运算符位运算位运算详解按位运算

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/65538.html

[LintCode] Binary Representation

摘要：细节上还要考虑正负号和整数位的越界情况。然后在循环内判断，如果有重复出现的，或者中小数部分的长度超过，就说明该小数无法完全转换。如果之前的正负号为，就在左边加上负号。 Problem Given a (decimal - e.g. 3.72) number that is passed in as a string, return the binary representation t...

you_De 2019-08-14 15:21 评论0 收藏0
[LintCode] Permutation Index I & Permutation I

摘要：我觉得虽然在里分类是，但其实是一道难题。思路如下搞一个哈希表，存储数组中每一位的后面小于它的数的个数。与上一题的不同之处时会有重复的数。当然，每个重复数的都要阶乘，例如有个，个，就是。是所有排列的次数和，返回下一次。 Permutation Index Problem Given a permutation which contains no repeated number, find...

lucas 2019-08-14 16:23 评论0 收藏0
javascript实现一些算法题

摘要：字符的左右移动给定一个字符串，这个字符串为号和个字母的任意组合。题目二在一个字符串中找到第一个只出现一次的字符。乘除模拟位运算真正位运算输入一个整数，求从到这个整数的十进制表示中出现的次数。字符的左右移动给定一个字符串，这个字符串为号和26个字母的任意组合。现在需要把字符串中的号都移动到最左侧，而把字符串中的字母移到最右侧并保持相对顺序不变，要求时间复杂度和空间复杂度最小。 var...

DirtyMind 2019-08-19 17:59 评论0 收藏0
[LintCode/LeetCode] Construct Binary Tree from Tr

摘要：做了几道二分法的题目练手，发现这道题已经淡忘了，记录一下。这道题目的要点在于找的区间。边界条件需要注意若或数组为空，返回空当前进到超出末位，或超过，返回空每次创建完根节点之后，要将加，才能进行递归。 Construct Binary Tree from Inorder and Preorder Traversal Problem Given preorder and inorder t...

马忠志 2019-08-14 15:40 评论0 收藏0
[LintCode/LeetCode] Count Binary Substrings

Problem Give a string s, count the number of non-empty (contiguous) substrings that have the same number of 0s and 1s, and all the 0s and all the 1s in these substrings are grouped consecutively. Subs...

BaronZhang 2019-08-16 12:44 评论0 收藏0