[LintCode] Count 1 in Binary [典型位運算題目]

ZHAO_ 發布于2019-08-14 15:16 / 430人閱讀

摘要：這道題，給我解決了兩個疑問，還剩一個。首先是要用無符號右移運算符，其次是可以用一個不斷左移的二進制作為參照。

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

云服務器 GPU云服務器 in運算符位運算位運算詳解按位運算

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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