Блог пользователя LashaBukhnikashvili

what is the complexity of Bitwise operations?
Автор LashaBukhnikashvili, 11 лет назад, По-английски

what is the complexity of Bitwise operations( &, |, ^, ~, <<, >> ) ?

thank you in advance.

  • Проголосовать: нравится
  • +5
  • Проголосовать: не нравится

»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

O(1). They are obviously faster than +, -, *, /.

→ Ответить
»
11 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

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.

→ Ответить
  • »
    »
    4 года назад, # ^ |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    How it work?

    I mean how it can do it in o(1) ?

    → Ответить
    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

      → Ответить
»
11 лет назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

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.

→ Ответить