資訊專欄INFORMATION COLUMN
摘要：依次移位復(fù)雜度思路依次移動位數(shù)進行計算。代碼利用性質(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).
For example, the 32-bit integer ’11" has binary representation 00000000000000000000000000001011, so the function should return 3.
復(fù)雜度
O(N), O(1), N = number of bits in the interger
思路
依次移動位數(shù)進行計算。
The unsigned right shift operator ">>>" shifts a zero into the leftmost position, while the leftmost position after ">>" depends on sign extension.
So when the first bit is 1, if use >>, 1 will always be there, then the loop will never end.
代碼
public int hammingWeight(int n) {
int cnt = 0;
while(n != 0) {
if((n & 1) == 1) {
cnt ++;
}
// must use unsigned operation
n = n >>> 1;
}
return cnt;
}
利用性質(zhì) n & (n - 1)
復(fù)雜度
O(N), O(1)， N = number of 1 bits in the number
思路
consider n & (n - 1) always eliminates the least significant 1.
代碼
public int hammingWeight(int n) {
int cnt = 0;
// loop times = number of 1"s in the n
while(n != 0) {
n = n & (n - 1);
cnt ++;
}
return cnt;
}
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/65226.html
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...
摘要：在線網(wǎng)站地址我的微信公眾號完整題目列表從年月日起，每天更新一題，順序從易到難，目前已更新個題。這是項目地址歡迎一起交流學(xué)習(xí)。 這篇文章記錄我練習(xí)的 LeetCode 題目，語言 JavaScript。 在線網(wǎng)站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公眾號： showImg(htt...
摘要：微信公眾號記錄截圖記錄截圖目前關(guān)于這塊算法與數(shù)據(jù)結(jié)構(gòu)的安排前。已攻略返回目錄目前已攻略篇文章。會根據(jù)題解以及留言內(nèi)容，進行補充，并添加上提供題解的小伙伴的昵稱和地址。本許可協(xié)議授權(quán)之外的使用權(quán)限可以從處獲得。 Create by jsliang on 2019-07-15 11:54:45 Recently revised in 2019-07-15 15:25:25 一 目錄 不...
摘要：月下半旬攻略道題，目前已攻略題。目前簡單難度攻略已經(jīng)到題，所以后面會調(diào)整自己，在刷算法與數(shù)據(jù)結(jié)構(gòu)的同時，攻略中等難度的題目。 Create by jsliang on 2019-07-30 16:15:37 Recently revised in 2019-07-30 17:04:20 7 月下半旬攻略 45 道題，目前已攻略 100 題。 一 目錄 不折騰的前端，和咸魚有什么區(qū)別...
摘要：重復(fù)此步驟直到原數(shù)歸零。注意右移運算符是算術(shù)右移，如果符號位是的話最高位將補，符號位是的話最高位補。當原數(shù)不為時，將原數(shù)與上原數(shù)減一的值賦給原數(shù)。因為每次減一再相與實際上是將最左邊的給消去了，所以消去幾次就有幾個。 Number of 1 Bits Write a function that takes an unsigned integer and returns the numbe...
閱讀 1637·2019-08-30 15:54
閱讀 2383·2019-08-30 15:52
閱讀 2067·2019-08-29 15:33
閱讀 3047·2019-08-28 17:56
閱讀 3245·2019-08-26 13:54
閱讀 1680·2019-08-26 12:16
閱讀 2455·2019-08-26 11:51
閱讀 1655·2019-08-26 10:26
