what is the complexity of Bitwise operations( &, |, ^, ~, <<, >> ) ?
thank you in advance.
what is the complexity of Bitwise operations( &, |, ^, ~, <<, >> ) ?
thank you in advance.
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3676 |
| 2 | Kevin114514 | 3659 |
| 3 | jiangly | 3640 |
| 4 | turmax | 3450 |
| 5 | tourist | 3408 |
| 6 | strapple | 3360 |
| 7 | Um_nik | 3354 |
| 8 | squareOf105 | 3348 |
| 9 | maroonrk | 3312 |
| 10 | idontwannadothis…e | 3191 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 155 |
| 2 | nik_exists | 151 |
| 3 | maspy | 149 |
| 4 | AmShZ | 145 |
| 5 | Um_nik | 143 |
| 6 | Errichto | 139 |
| 7 | BledDest | 136 |
| 8 | adamant | 135 |
| 9 | maroonrk | 133 |
| 10 | cry | 130 |
O(1). They are obviously faster than +, -, *, /.
An answer you might want is O(1) or "constant time", in terms of the number of processor ticks per operation.
For a more detailed view, you may also find these tables interesting: gmplib.org/%7Etege/x86-timing.pdf.
How it work?
I mean how it can do it in o(1) ?
The same way it does addition.
For example, "bitwise xor" is binary addition without carry, just as "addition" is binary addition with carry. To wonder how to do one is the same as to wonder how to do the other. If you are interested in the specifics, a google search like this will help.
when you say the complexity of +, -, and two more expensive functions /, * are O(1); so while they are much slower than &,|,^,~,<<,>> so they are O(1) too.but of course when you check them more definitely you can see +, — are O(log) (= log 2 ^ 32 or 64 => 32 or 64), and * is O(log ^ 2) (32 ^ 2 or 64 * 2) and i don't know what "/" does to discuss about the complexity :D.and for this reason you say the processors do about 10 ^ 8 operations per second while it is much more(about 10 ^ 12 i think anyone who knows the exact number plz say it).so you can see using assembly and other low-level languages can cause more optimization(because you declare your own functions and prevent from unnecessary operation)while it causes more more code than usual.