C: Setting the i'th bit of an integer to 1 in O(1)

Question

Now, I know the way to set the i'th bit of a number is use the shift operator to shift 1 till you reach the required bit, and then just or it with the number. But this process is O(length of number) because shifting a number to the i'th position is like traversing until there, right? Please correct me if I'm wrong.

Here is my code:

x = x| (1<<i)

Is there a way to do this in O(1)? In other words, how does one get direct access to the bits in a number? I'm thinking along the lines of array indexing.

It depends on your hardware, i.e. CPU. Show your code and the **relevant** machine code. But you can use a lookup-table to be on the safe (but possibly slower) side. — too honest for this site, Feb 23 '17 at 13:32
How is this operation O(1)? It will have to go traverse the number, right? — Mahathi Vempati, Feb 23 '17 at 13:33
@Tinkidinki There is no need to traverse the number. The shift operation usually requires one low-level command — Vlad from Moscow, Feb 23 '17 at 13:36
Just use it as you have it. I dont see why it should not be 0(1) operation. There is no loop or whatever. Also on some cpus or microcontrollers this line is converted into single instruction. — ttdado, Feb 23 '17 at 13:40
@VladfromMoscow, so I am to understand that shifting 1 how many ever positions is always O(1) and doesnt depend on i at all? — Mahathi Vempati, Feb 23 '17 at 13:40
@Tinkidinki yes. For more bits operations also see http://stackoverflow.com/questions/47981/how-do-you-set-clear-and-toggle-a-single-bit-in-c-c?rq=1 — ttdado, Feb 23 '17 at 13:42
Bit shift is O(1), just like addition is O(1). When adding *n* to *m*, you don't have to increment *m* *n* times. The same goes with bit shifting. — el.pescado - нет войне, Feb 23 '17 at 13:46
@el.pescado, thanks for the anology, that makes a lot of sense to me!!! — Mahathi Vempati, Feb 23 '17 at 13:53
Definitive answers are inherently wrong because all this depends on is *your definition* of what the elementary operations are. Sure, bit shifts by a variable amount are commonly accepted as elementary, but it's always a choice that you make, even if you do it implicitly. — harold, Feb 23 '17 at 14:58

score 5 · Accepted Answer · edited May 23 '17 at 12:25

5

Shifting 1 by k bits is done in hardware. At a grossly simplified level, an n-bit CPU has n registers that represent a number shifted by 0, 1, 2, ..., n-1 bits in each direction. When a shift operation is executed, CPU loads the number in a register k based on the number of shifts, and reads the output in the next cycle. This makes bit shifting an O(1) operation.

This Q&A has a diagram explaining the hardware behind the O(1) "magic" of modern CPUs using multiplexers.

edited May 23 '17 at 12:25

Community

1
1

answered Feb 23 '17 at 13:39

Sergey Kalinichenko

714,442
84
1,110
1,523

Thanks!!! but from the diagram, i infer that for a 2^i bit system, i need i layers of circuitry, right? So shift is done in constant time for a given system. – Mahathi Vempati Feb 23 '17 at 13:51
@Tinkidinki Yes, barrel shifter needs `i` layers for 2^i-bit system. However, all `i` layers are active at the same time, so even though we are talking about `i` gate delays, the operation completes in a single cycle (which is, of course, much longer than gate delays). – Sergey Kalinichenko Feb 23 '17 at 13:56
Not all processors have barrel shifter... P4 didn't. – Antti Haapala -- Слава Україні Feb 23 '17 at 14:54

Toby · Answer 2 · 2017-02-23T14:07:18.350

2

As others have pointed out n |= 1 << i is not O(n). This is because a bit shift operation in most CPU's is a single instruction, on the ones I am familiar with at the moment it takes a cycle or two IIRC.

If however, you are introducing a loop within your C code, then this of course, will be O(n), such as:

n = 1;
for(j = 0; j < i; ++j)
    n <<= 1;
x |= n;

For a refactored bit setting for generically setting a bit in an integer value, you could do something like:

typedef enum x_bits_e {
    x_bit1 = 1 << 0;
    x_bit2 = 1 << 1;
    x_bit3 = 1 << 2; 
     // and so on
};

int16_t set_bit_in_x(int16 x, x_bits_e i)
{ 
    return x | i;
}

edited Feb 23 '17 at 14:07

answered Feb 23 '17 at 13:36

Toby

9,696
16
68
132

Any reason for the down-vote? – Toby Feb 23 '17 at 13:39
No problem. I can up-vote your answer.:) – Vlad from Moscow Feb 23 '17 at 13:41
i didnt, but you could improve naming somehow – ttdado Feb 23 '17 at 13:41
Ha, thanks @VladfromMoscow, really just curious as to how specifically the answer could be improved tbh – Toby Feb 23 '17 at 13:42
1

P4 didn't have a barrel shifter – Antti Haapala -- Слава Україні Feb 23 '17 at 14:54

C: Setting the i'th bit of an integer to 1 in O(1)

2 Answers2