LashaBukhnikashvili's blog

what is the complexity of Bitwise operations?
By LashaBukhnikashvili, 11 years ago, In English

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

thank you in advance.

  • Vote: I like it
  • +5
  • Vote: I do not like it

»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
11 years ago, # |
  Vote: I like it +6 Vote: I do not like it

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.

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    How it work?

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

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
»
11 years ago, # |
  Vote: I like it +14 Vote: I do not like it

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.

→ Reply