資訊專欄INFORMATION COLUMN
摘要：重復(fù)此步驟直到原數(shù)歸零。注意右移運(yùn)算符是算術(shù)右移，如果符號(hào)位是的話最高位將補(bǔ)，符號(hào)位是的話最高位補(bǔ)。當(dāng)原數(shù)不為時(shí)，將原數(shù)與上原數(shù)減一的值賦給原數(shù)。因?yàn)槊看螠p一再相與實(shí)際上是將最左邊的給消去了，所以消去幾次就有幾個(gè)。
Number of 1 Bits
移位法 復(fù)雜度Write a function that takes an unsigned integer and returns the number of ’1" bits it has (also known as the Hamming weight).
For example, the 32-bit integer ’11" has binary representation 00000000000000000000000000001011, so the function should return 3.
時(shí)間 O(1) 空間 O(1)
思路通過(guò)與運(yùn)算符判斷最低位/最高位是否是1，然后再右移/左移。重復(fù)此步驟直到原數(shù)歸零。
注意右移運(yùn)算符是算術(shù)右移，如果符號(hào)位是1的話最高位將補(bǔ)1，符號(hào)位是0的話最高位補(bǔ)0。在C/C++中可以先將原數(shù)轉(zhuǎn)換成無(wú)符號(hào)整數(shù)再處理，而在Java中可以使用無(wú)符號(hào)右移算術(shù)符>>>。當(dāng)然，左移的解法就沒(méi)有這個(gè)問(wèn)題了。
代碼public class Solution {
// you need to treat n as an unsigned value
public int hammingWeight(int n) {
int mark = 0b1, count = 0;
while(n != 0b0){
if((n & mark)==0b1){
count++;
}
n = n >>> 1;
}
return count;
}
}
減一相與法
復(fù)雜度
時(shí)間 O(1) 空間 O(1)
思路該方法又叫Brian Kernighan方法。當(dāng)原數(shù)不為0時(shí)，將原數(shù)與上原數(shù)減一的值賦給原數(shù)。因?yàn)槊看螠p一再相與實(shí)際上是將最左邊的1給消去了，所以消去幾次就有幾個(gè)1。比如110，減去1得101，相與得100，消去了最左邊的1。
代碼public class Solution {
// you need to treat n as an unsigned value
public int hammingWeight(int n) {
int count = 0;
while(n != 0b0){
n = n & (n - 1);
count++;
}
return count;
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/64427.html
摘要：依次移位復(fù)雜度思路依次移動(dòng)位數(shù)進(jìn)行計(jì)算。代碼利用性質(zhì)復(fù)雜度，思路代碼 LeetCode[191] Number of 1 Bits Write a function that takes an unsigned integer and returns the number of ’1 bits it has (also known as the Hamming weight). Fo...
Problem Number of 1 BitsWrite a function that takes an unsigned integer and returns the number of ’1 bits it has (also known as the Hamming weight). Example For example, the 32-bit integer 11 has bina...
摘要：題目鏈接題目分析對(duì)給定范圍內(nèi)的每個(gè)整數(shù)，返回其二進(jìn)制形式下，數(shù)字出現(xiàn)的次數(shù)為質(zhì)數(shù)的次數(shù)。思路由于題目固定了范圍為，次方為千萬(wàn)。即最多只會(huì)出現(xiàn)次。存在則符合題目要求的數(shù)字，否則不計(jì)入該數(shù)字。最終代碼若覺(jué)得本文章對(duì)你有用，歡迎用愛(ài)發(fā)電資助。 D57 762. Prime Number of Set Bits in Binary Representation 題目鏈接 762. Prime ...
摘要：題目漢明距離是兩個(gè)字符串對(duì)應(yīng)位置的不同字符的個(gè)數(shù)，這里指二進(jìn)制的不同位置例子我的解法先將，進(jìn)行異位或運(yùn)算再轉(zhuǎn)化成二進(jìn)制然后把去掉算出長(zhǎng)度其他方法先算出不同位數(shù)，然后用右移運(yùn)算符算出能右移幾次來(lái)獲取距離 1題目 The Hamming distance between two integers is the number of positions at which the corresp...
摘要：思路一比特位移動(dòng)將比特位逆轉(zhuǎn)過(guò)來(lái)也就是將十進(jìn)制數(shù)轉(zhuǎn)化為二進(jìn)制數(shù)，再?gòu)挠彝螳@得每一位上的值，再將這個(gè)值添加至結(jié)果值中。根據(jù)分治思想，逆轉(zhuǎn)個(gè)比特位等價(jià)于分別將每個(gè)比特位進(jìn)行逆轉(zhuǎn)。 題目要求 Reverse bits of a given 32 bits unsigned integer. For example, given input 43261596 (represented in...
閱讀 1114·2021-09-22 15:37
閱讀 1141·2021-09-13 10:27
閱讀 2485·2021-08-25 09:38
閱讀 2456·2019-08-26 11:42
閱讀 1538·2019-08-26 11:39
閱讀 1565·2019-08-26 10:58
閱讀 2330·2019-08-26 10:56
閱讀 2578·2019-08-23 18:08
