//
// E_191_NumberOf1Bits.swift
// AlgorithmLeetCode
//
// Created by okerivy on 2017/3/9.
// Copyright ? 2017年 okerivy. All rights reserved.
// https://leetcode.com/problems/number-of-1-bits
import Foundation
// MARK: - 題目名稱: 191. Number of 1 Bits
/* MARK: - 所屬類別:
標(biāo)簽: Bit Manipulation
相關(guān)題目:
(E) Reverse Bits
(E) Power of Two
(M) Counting Bits
(E) Binary Watch
(E) Hamming Distance
*/
/* MARK: - 題目英文:
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.
*/
/* MARK: - 題目翻譯:
編寫一個(gè)函數(shù)馆揉，它接收一個(gè)無符號(hào)整數(shù)并返回它二進(jìn)制形式中 '1'的個(gè)數(shù)(也稱為Hamming weight)窟赏。
例如，整數(shù) ‘11’ 的32位二進(jìn)制表示形式為 00000000000000000000000000001011 型诚，所以函數(shù)應(yīng)當(dāng)返回3。
*/
/* MARK: - 解題思路:
考慮位運(yùn)算
設(shè)輸入的數(shù)為n徘六，把n與1做二進(jìn)制的與&(AND)運(yùn)算锄贼，即可判斷它的最低位是否為1。
如果是的話注簿，把計(jì)數(shù)變量加一契吉。然后把n向右移動(dòng)一位，重復(fù)上述操作诡渴。
當(dāng)n變?yōu)?時(shí)捐晶，終止算法，輸出結(jié)果妄辩。
*/
/* MARK: - 復(fù)雜度分析:
時(shí)間復(fù)雜度：O(n) 空間復(fù)雜度：O(1)
*/
// MARK: - 代碼:
private class Solution {
// 取模 整除
func hammingWeight(_ n: UInt32) -> Int {
// 傳進(jìn)來n為let類型 不能改變,所以搞個(gè)num變量
var num = n
// 計(jì)數(shù)器
var count = 0
while num > 0 {
// 把num與1做二進(jìn)制的與(AND)運(yùn)算惑灵，即可判斷它的最低位是否為1
if num & 1 == 1 {
count += 1
}
// 右移一位 相當(dāng)于 / 2 public func >>=(lhs: inout UInt32, rhs: UInt32)
num >>= 1
}
return count;
}
// 取模 整除
func hammingWeight2(_ n: UInt32) -> Int {
// 傳進(jìn)來n為let類型 不能改變,所以搞個(gè)num變量
var num = n
// 計(jì)數(shù)器
var count = 0
while num > 0 {
count += 1
// x & (x - 1) 它會(huì)把整數(shù)x的二進(jìn)制的最后一個(gè)1去掉。
num &= (num - 1)
}
return count;
}
}
// MARK: - 測(cè)試代碼:
func numberOf1Bits() {
print(Solution().hammingWeight(0))
print(Solution().hammingWeight(1))
print(Solution().hammingWeight(2))
print(Solution().hammingWeight(8))
print(Solution().hammingWeight(11))
print(Solution().hammingWeight(7))
}
