Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Looking for a method to calculate what number are used to make a number

  1. Apr 28, 2010 #1
    I am getting a file from a system and in one column there is a number. This number is a sum of predetermined 15 numbers.
    The 15 predetermined numbers (bits) are 1 2 4 8 16 32 64 128 256 512 1024 ...,
    Each predetermined number can only be used once in the total number.

    So if the number is given is 530, I know 512, 16, 2 were used.

    Is there a formula to calculate the values used to make the number?

    Thanks,
     
  2. jcsd
  3. Apr 28, 2010 #2
    There is a key point here...

    sum(k = 0 to n) of 2^k = 2^(n+1) - 1; [for example, 2^0 + 2^1 + 2^2 = 7 = 2^3 - 1]

    To see how this helps, try making a number without including the greatest bit that is less than the number, eg. try making the sum reach 17 without using 16 in the sum.

    This should demonstrate there is a good algorithm which will always give you the answer. (neat problem)
     
  4. Apr 28, 2010 #3
    Well I am assuming you are a computer scientist. You should know how to convert a number from decimal to binary right?

    530 / 2 = 265 R 0
    265 / 2 = 132 R 1
    132 / 2 = 66 R 0
    66 / 2 = 33 R 0
    33 / 2 = 16 R 1
    16 / 2 = 8 R 0
    8 / 2 = 4 R 0
    4 / 2 = 2 R 0
    2 / 2 = 1 R 0
    1 / 2 = 0 R 1

    So this is the bit string
    1000010010

    And each position in the bit string matches up to a certain power of 2.

    So just reduce the number to a bit string and then get the positions of the 1s in the bit string and you will know which powers of 2 make up your number.
     
  5. Apr 28, 2010 #4
    Thanks guys,
    No, I am a network admin jumping out of my pool a bit :-)
     
  6. Apr 29, 2010 #5

    Borek

    User Avatar

    Staff: Mentor

    You are network admin and you don't see binary number when you are shown one?

    [URL]http://www.bpp.com.pl/IMG/faint.gif[/URL]

    http://en.wikipedia.org/wiki/Positional_system
     
    Last edited by a moderator: Apr 25, 2017
  7. Apr 29, 2010 #6
    When you have a number in an integer variable, it is already in binary and there is no need to convert it further.

    Most programming languages have an AND operator which performs an AND operation between the bits of two operands. In the C programming language, the operator is called &. For example, to determine if bit 8 is set, you would use the expression something&256. Some microprocessors also have instructions that count the number of most significant or least significant zero bits. On an Intel processor, these instructions are named BSF and BSR. The BSF instruction determines the bit position of the lowest set bit in a register, while the BSR instruction determines the bit position of the highest set bit. If you are programming in assembly language on an Intel processor, you can enumerate all the bits by using the BSF instruction to find the first set bit, clear it using the BTR instruction and repeat until no more bits are found. To determine if a specific bit is set using the bit position, use the BT instruction. In the C programming lanaguage, the expression something&(1<<position) accomplishes the same function.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook