title: Time Complexity of bit operations
body: <p>As a result of some original research and the need to develope tools for it I've come up with some new and I hope better/quicker ways of performing certain mathematical operations. Atm I'm working on the psuedocode to post them on the site in response to questions which have already been asked.</p>
  
  <p>However before I do that I want to optimise them as much as possible and so I need someone to clarify how bit operations work from a time complexity perspective.</p>
  
  <p>For example say I want to evaluate which of two 8 bit integers is larger. I'm using 8 bits as an example but in reality they could be much larger.  </p>
  
  <h2>10000100</h2>
  
  <h2>10100000</h2>
  
  <p>As it stands the relation operator can be evaluated having compared the 6 MSB's.
  Notionally I could subtract 10000000 from both without affecting the inequality.</p>
  
  <h2>00100000</h2>
  
  <h2>00000100</h2>
  
  <ul>
  <li>Q1. This would speed up the evaluation of the relation operator if
  the reading starts from the MSB but does it or do the leading 0's
  have to be evaluated anyway? Obvioulsy subtracting isn't worth doing
  since subtracting 10000000 is itself a 8 bit operation but say
  instead I could set the MSB or specific bit's using a single or two
  bit operation then it could be worthwhile.</li>
  <li>Q2. Two methods I can    think of that might fit the bill are
  bitshifting left and then right    to destroy the leading 1 or using
  a mask but are there other methods?    I'm particularly interested in
  ones which might let you set any bit    not just the leading bits. If
  it's specific to a certain language    just let me know that please.</li>
  <li>Q3. Since masks are N bits then is    using a mask not an N bit
  operation itself?</li>
  <li>Q4. What about evaluating    a specific bit, what methods exist and
  how time complex is the    operation? Do all proceeding bits have to
  be read in first so that    it's a N bit operation or can you "jump"
  to a certain bit?</li>
  <li>Q5 Two    strings being conjugated from a time complexity
  perspective. Does    that happen by associating two memory addresses
  together or does one    string get read and copied into the other so
  that it's a  String.length operation?</li>
  </ul>
  
  <p>Thanks.  </p>
  
  <p>Further clarification.
  I've been rereading the notes I pulled from a few places and although Dukeling confirmed what I thought should be the case I need to triple check. Take for example the simple multiplication algorithm. I see in numerous places the claim that this is a Log^2(N) operation and the given reason for it being a Log^2(N) operation is due to it consisting of Log(N) additions of a Log(N) number. The problem I have with this is although that is true it ignores the fact that each of those Log(N) numbers will be the result of a bit shift and by the end we will have bitshifted at least Log(N) times. As bitshift by 1 is a Log(N) operation the bitshifts considered alone give us Log^2(N) operations. It therefore makes no sense to me when I see it further claimed that in practice multiplication doesn't in fact use Log^2(N) operations as various methods can reduce the number of required additions. Since the bitshifting alone gives us Log^2(N) I'm left confused as to how that claim can be true.</p>