Notices
Results 1 to 1 of 1

Thread: Bit-wise Nth Binary Digit Algorithm

  1. #1 Bit-wise Nth Binary Digit Algorithm 
    New Member
    Join Date
    Aug 2006
    Posts
    1
    I've been working on this algorithm or another that requires the Nth binary digit of a sum of bits to be expressed as a logical consequence of the values of these bits. What I mean is, say that I have a bunch of bits (B1,B2,B3,B4), each of which can be 1 or 0. If I want the 1st digit of their sum, that's no problem: B1 (X) B2 (X) B3 (X) B4, (X) being Xor. But say I want the 2nd digit? Now okay, I can do this by hand: ((B1xB2x~B3x~B4)|(B1xB2xB3x~B4)|(B1xB2x~B3x~b4)|.. .) And so forth and so on explicitly all possibilities that have exactly two or three of the bits as "true". But this particular expansion only works for 4 bits, and I could easily have 5, or 456, or even 10^400 bits could theoretically be required for analysis. What's more, it would be highly inefficient for me to jump in and manually make this expansion every time the algorithm is run.

    So is there an algorithm for efficiently doing this? Of what complexity would it be?


    Reply With Quote  
     

  2.  
     

Bookmarks
Bookmarks
Posting Permissions
  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •