search

KyrieSu / Code_cpp

0 stars 0 forks source link

010. Power of Four #10

Open KyrieSu opened 8 years ago

KyrieSu commented 8 years ago

Given an integer (signed 32 bits), write a function to check whether it is a power of 4.

Example:

Given num = 16, return true. Given num = 5, return false.

Follow up:

Could you solve it without loops/recursion?

KyrieSu commented 8 years ago

一開始我以為只有right shift兩位這麼簡單，但好像沒怎麼簡單XD

LarryLuTW commented 8 years ago

我有想到一個好解法 給你一點提示 0001 0010 0100 1000 這些都是二的次方數 但只有 0001 0100 是四的次方數

所以先確認是不是二的次方數 然後再判斷那個 1 的位置就可以了

KyrieSu commented 8 years ago

恩恩 看出來了 只要4的次方，1的位置一定再奇數的index~

感覺這題有點簡單了 哈哈

LarryLuTW commented 8 years ago

嗯嗯不過你怎麼確認是不是在奇數 index

KyrieSu commented 8 years ago

好問題......

LarryLuTW commented 8 years ago

也是用位元運算 O(1) 就可以算出來

LarryLuTW commented 8 years ago

這題再想一下 我明天寫解法

KyrieSu commented 8 years ago

OK 我都忘記有這題了　哈哈

LarryLuTW commented 8 years ago

接續上面的 先確認是不是二的次方數 然後再判斷 1 的位置就好了

4 -> 00000100 16 -> 00010000 64 -> 01000000

那要怎麼判斷那個 1 在哪裡呢 就跟 01010101 做 and 運算 如果結果是 0 就代表他的 1 不在奇數位 => 只是 2 的次方而不是 4 的次方 反之就是 4 的次方

至於要怎麼製造出 010101... 這個整數 要慢慢拼很麻煩 因為 0101 可以寫成 5 一個 hex 代表 4 個位元 所以可以直接 int n = 0x55555555 這樣就可以得到 01010101...(0 跟 1 各 16 個)

w5151381guy commented 8 years ago

我這題打完了>< 自己有稍微測一下是對的XDD 再麻煩Larry幫我看有哪邊要修改摟~~~

LarryLuTW commented 8 years ago

我剛剛看完還滿棒的 沒什麼需要改的XD