[LintCode] Count 1 in Binary [典型位運(yùn)算題目]

ZHAO_ 發(fā)布于2019-08-14 15:16 / 478人閱讀

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

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給我解決了兩個(gè)疑問，還剩一個(gè)。首先是要用無符號右移運(yùn)算符>>>，其次是可以用一個(gè)不斷左移的二進(jìn)制1作為參照。那么如何獲得一個(gè)用1來進(jìn)行補(bǔ)位的左移的1呢？
第一種解法，num右移，每次對末位進(jìn)行比較，直到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

云服務(wù)器 GPU云服務(wù)器 in運(yùn)算符位運(yùn)算位運(yùn)算詳解按位運(yùn)算

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://www.ezyhdfw.cn/yun/65538.html

相關(guān)文章

[LintCode] Binary Representation

摘要：細(xì)節(jié)上還要考慮正負(fù)號和整數(shù)位的越界情況。然后在循環(huán)內(nèi)判斷，如果有重復(fù)出現(xiàn)的，或者中小數(shù)部分的長度超過，就說明該小數(shù)無法完全轉(zhuǎn)換。如果之前的正負(fù)號為，就在左邊加上負(fù)號。 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

摘要：我覺得雖然在里分類是，但其實(shí)是一道難題。思路如下搞一個(gè)哈希表，存儲(chǔ)數(shù)組中每一位的后面小于它的數(shù)的個(gè)數(shù)。與上一題的不同之處時(shí)會(huì)有重復(fù)的數(shù)。當(dāng)然，每個(gè)重復(fù)數(shù)的都要階乘，例如有個(gè)，個(gè)，就是。是所有排列的次數(shù)和，返回下一次。 Permutation Index Problem Given a permutation which contains no repeated number, find...

lucas 2019-08-14 16:23 評論0 收藏0
javascript實(shí)現(xiàn)一些算法題

摘要：字符的左右移動(dòng)給定一個(gè)字符串，這個(gè)字符串為號和個(gè)字母的任意組合。題目二在一個(gè)字符串中找到第一個(gè)只出現(xiàn)一次的字符。乘除模擬位運(yùn)算真正位運(yùn)算輸入一個(gè)整數(shù)，求從到這個(gè)整數(shù)的十進(jìn)制表示中出現(xiàn)的次數(shù)。字符的左右移動(dòng) 給定一個(gè)字符串，這個(gè)字符串為號和26個(gè)字母的任意組合?，F(xiàn)在需要把字符串中的號都移動(dòng)到最左側(cè)，而把字符串中的字母移到最右側(cè)并保持相對順序不變，要求時(shí)間復(fù)雜度和空間復(fù)雜度最小。 var...

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

摘要：做了幾道二分法的題目練手，發(fā)現(xiàn)這道題已經(jīng)淡忘了，記錄一下。這道題目的要點(diǎn)在于找的區(qū)間。邊界條件需要注意若或數(shù)組為空，返回空當(dāng)前進(jìn)到超出末位，或超過，返回空每次創(chuàng)建完根節(jié)點(diǎn)之后，要將加，才能進(jìn)行遞歸。 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