Is bit shifting O(1) or O(n)?

language-agnostic big-o cpu hardware bit-shift
Pacerier picture Pacerier · Jan 31, 2012 · Viewed 13k times · Source

Are shift operations O(1) or O(n) ?

Does it make sense that computers generally require more operations to shift 31 places instead of shifting 1 place?

Or does it make sense the number of operations required for shifting is constant regardless of how many places we need to shift?

PS: wondering if hardware is an appropriate tag..

Answer

dan04 picture dan04 · Jan 31, 2012

A barrel shifter allows the shift to be performed in O(log n) passes — which may be done in the same clock cycle, making shifting an O(1) operation.

Related questions

Given an array of positive and negative integers, re-arrange it so that you have positive integers on one end and negative integers on other

I recently came across a Microsoft Interview Question for Software Engineer. Given an array of positive and negative integers, re-arrange it so that you have positive integers on one end and negative integers on other, but retain their order of …

Read More
Can hash tables really be O(1)?

It seems to be common knowledge that hash tables can achieve O(1), but that has never made sense to me. Can someone please explain it? Here are two situations that come to mind: A. The value is an int smaller …

Read More
Complexity when generating all combinations

Interview questions where I start with "this might be solved by generating all possible combinations for the array elements" are usually meant to let me find something better. Anyway I would like to add "I would definitely prefer another solution …

Read More