C++面試八股文之位運算問題詳解
面試中
某日二師兄參加XXX科技公司的C++工程師開發(fā)崗位第12面:
面試官:了解位運算嗎?
二師兄:了解一些。(我很熟悉)
面試官:請列舉以下有哪些位運算?
二師兄:按位與(&
)、按位或(|
)、按位異或(^
),按位取反(~
)、左移(<<
)和右移(>>
)。
面試官:好的。那你知道位運算有什么優(yōu)勢嗎?
二師兄:優(yōu)勢主要有兩點:1.速度快。2.節(jié)省寄存器/內(nèi)存空間。
面試官:在C++中,如何處理int
型負數(shù)最高位(是1
)的左移或者右移?
二師兄:不同編譯器處理的方法不同。此操作在C++中屬于未定義的行為。所以不要使用帶符號的整數(shù)參加位運算。
面試官:如何判斷一個數(shù)是不是2的整數(shù)次方?
二師兄:使用這個數(shù)與這個數(shù)-1按位與,如果結果是0,則這個數(shù)是2的整數(shù)次方,否則不是。
bool is_power_of_two(unsigned int n) { return n & (n-1) == 0; }
面試官:如何使用位運算交換兩個數(shù),而不能申請額外的空間?
二師兄:可以使用異或操作,原理是一個數(shù)異或兩次同一個數(shù),結果等于原值。
void swap(unsigned int& a, unsigned int& b) { a = a ^ b; // a = a ^ b; b = a ^ b; // b = a ^ b ^ b = a; a = a ^ b; // a = a ^ b ^ a = b; }
面試官:如何獲取一個數(shù)字中的某一位是0
還是1
?
二師兄:把這個數(shù)字右移x
位,然后與&1
。
bool get_bit(unsigned int n, unsigned int x) { return 1 & (n >> x); }
面試官:如何將一個數(shù)的某一位置成1
/置成0
,或取反?
二師兄:沉思良久。。。想不起來了。。。
今日二師兄的表現(xiàn)還不錯,除了最后一問,其他都答上來了。讓我們看看最后一問吧:
如何將一個數(shù)的某一位置成0/置成1,或取反?
先看第一個,如何將一個數(shù)的某一位置成1
?這個數(shù)的這一位要不是1
要不是0
,最終要變成1
,那么可以考慮在這一位上構造個1
,然后和這個數(shù)或,這一位就置成了1
。
unsigned set_bit_1(unsigned int n, unsigned int x) { return (1u << x) | n; }
如何將一個數(shù)的某一位置成0
呢?我們首先考慮到與(&
)操作。同樣我們需要構造出來一個全是1
的數(shù)字,然后再這一位上變成0
,并與傳入的參數(shù)進行與操作:
unsigned set_bit_0(unsigned n, unsigned x) { return (~(1u << x)) & n; }
最后一個問題,如果講一個數(shù)的某一位取反?想到了取反,我們就想到了異或。任何數(shù)與1
異或等于取反,任何數(shù)與0
異或等于原數(shù):
unsigned flip_bit(unsigned n, unsigned x) { return (1u << x) ^ n; }
好了,今日份面試到這里就結束了。二師兄自我感覺表現(xiàn)還行,晚上給自己加了個雞腿。
更多關于C++位運算面試的資料請關注腳本之家其它相關文章!
相關文章
C++?基本數(shù)據(jù)類型中int、long等整數(shù)類型取值范圍及原理分析
這篇文章主要介紹了C++?基本數(shù)據(jù)類型中int、long等整數(shù)類型取值范圍及原理分析,具有很好的參考價值,希望對大家有所幫助。如有錯誤或未考慮完全的地方,望不吝賜教2022-11-11C語言sizeof與字符串處理與動態(tài)內(nèi)存分配及main函數(shù)參數(shù)詳解
這篇文章主要介紹了C語言字符串處理函數(shù)、sizeof、動態(tài)內(nèi)存分配函數(shù)、main函數(shù)參數(shù)問題,static在修飾變量的時候,如果是修飾全局變量,則跟全局變量功能一樣,通過示例代碼給大家介紹的非常詳細,需要的朋友可以參考下2022-07-07