language agnostic - Is bit shifting O(1) or O(n)? -

language agnostic - Is bit shifting O(1) or O(n)? -

good afternoon all,

i wondering shift operations o(1) or o(n) ?

basically curious, create sense computers require more operations shift 31 places instead of shifting 1 place?

or create sense number of operations required shifting constant regardless of how many places need shift?

ps: wondering if hardware appropriate tag..

some instruction sets limited 1 bit shift per instruction. , instruction sets allow specify number of bits shift in 1 instruction, takes 1 clock cycle on modern processors (modern beingness intentionally vague word). see dan04's answer barrel shifter, circuit shifts more 1 bit in 1 operation.

it boils downwards logic algorithm. each bit in result logic function based on input. single right shift, algorithm like:

if instruction [shift right] , bit 1 of input 1, bit 0 of result 1, else bit 0 0. if instruction [shift right], bit 1 = bit 2. etc.

but logic equation be:

if instruction [shift right] , amount operand 1, result bit 0 = shifted input bit 1. if amount 2 bit 0 = bit 2. and on.

the logic gates, beingness asynchronous, can of in 1 clock cycle. yet true single shift allows faster clock cycle , less gates settle, if comparing these 2 flavors of instruction. or alternative making take longer settle, instruction takes 2 or 3 clocks or whatever, , logic counts 3 latches result.

the msp430, example, has single bit rotate right instructions (because can perform single bit shift or rotate left instruction, leave reader figure out).

the arm instruction set allows both immediate , register based multi-bit rotates, arithmetic shifts , logical shifts. think there 1 actual rotate instruction , other alias, because rotate left 1 same rotate right 32, need 1 direction barrel shifter implement multi bit rotate.

shl in x86 allows more 1 bit per instruction, used take more 1 clock.

and on, can examine of instruction sets out there.

the reply question is not fixed. 1 operation, 1 cycle, 1 instruction. 1 instruction multiple clock cycles. multiple instructions, multiple clock cycles.

the compilers optimize these sorts of things. have 16 bit register instruction set swap byte instruction , , instruction immediate, single bit shift. may think shifting 8 bits require 8 shift instruction cycles, swap bytes (one instruction) , , lower half zeros (which might take 2 instructions, or might variable word length instruction of 2 words, or might encode single instruction) takes 2 or 3 instruction/clock cycles instead of 8. shift of 9 bits, can same thing , add together shift, making 9 clocks vs 3 or 4. also, on architectures, faster multiply 256 shift 8, etc, etc. each instruction set has own limitations , tricks.

it not case either instruction sets provide multi bit or limit single bit. processors fall "computer" category, x86, arm, powerpc, , mips, lean toward 1 operation shift. expand processors not "computers" commonly used today, , shifts other way, more of them single bit multi bit, multiple operations needed perform multi-bit shift.

language-agnostic hardware