HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Time Complexity of Shifting

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
shiftingcomplexitytime

Problem

I'm developing a IMHO very interesting algorithm for integer division. This algorithm uses boolean shifting(It shifts left for multiplication by 2). I'm wondering if << c is $O(c)$ or $O(n)$. I'm hearing it depends on architecture. Algorithms ideally should be architecture independent. So for the purposes of analysing the time complexity of my algorithm, should I consider << c as 1 primitive operation or c primitive operations.

I've looked at the other questions here, and they are saying it depends on the machine.

I'm using RAM model of computation, but don't want to assign << c a cost of 1 when it may in fact cost c.

Solution

Most of architectures use a single instruction for left and right shift.

Usually, this instruction (WLOG we condier only logical shift left) is LSL, the syntax is the following:

lsl $rd,$rs,#$offset


where rd is the registry in which load the variable, rs is the registry in which store the result and #offset is the number of bit to shift.

So you could consider the left or right shift operation as taking $O(1)$, because this operation takes only a single CPU's clock.

Code Snippets

lsl $rd,$rs,#$offset

Context

StackExchange Computer Science Q#67973, answer score: 6

Revisions (0)

No revisions yet.