• Roger Wolff (unregistered) in reply to AdT
    AdT:
    And an underestimation is obviously a lot worse than an overestimation.

    It depends on what you're doing. For example when you are converting an int to a float (when your hardware can't do that), you have to know the exact integer-part-of-log2 of the input. You're going to drop the highest bit (it isn't stored in the floating point fomat, as it's always 1). If that bit wasn't 1, you're suddenly handling a different number....

    Example: 1280 = 101 0000 0000b Highest 1-bit is 10, so you store exponent 10 (usually offset by 127 or something), and dropping the topmost 1-bit 01 0000 0000 (with extra zeroes tagged on at the end. This is correct.

    example: 2047 = 111 1111 1111 Highest 1-bit is 10, but suppose you overestimate this and say 11. Store exponent 11, and mantissa 111 1111 1111 and you end up with 4097 when you retrieve the resulting float.....

  • (unregistered)
  • CaptchaFillerOutEr (unregistered) in reply to Erwin Bolwidt

    You need at least one bit to represent zero.

  • Ross Presser (unregistered)

    Horribly unsafe version without bitshifting or division:

    unsigned int countbits(unsigned int x) {

    unsigned int nbits = 1; unsigned int tester = 1;

    while(tester < x) { tester += tester; nbits++; }

    :-)

  • Bob (unregistered)

    nbits = ceiling(sqrt(abs(range)))+1

  • Bob (unregistered) in reply to Bob

    If nbits is signed, if not remove the "+1".

  • (cs) in reply to Bob

    nbits = ceiling(sqrt(abs(range)))+1

    Sooo, if range is 10,000 ..... we need 101 bits?

  • Paul Pacheco (unregistered) in reply to Ancient_Hacker
    Ancient_Hacker:
    > How many test runs with what data sets one how many computers with how many compilers with how many different settings are needed, Ancient Hacker?

    You're playing a losing game. There is no number of tests that can "prove" a shaky bit of code.

    Not my proverb-- You might recall Dijkstra famous statement: that software testing cannot prove that there are no errors in your code; it can only demonstrate that they exist.

    Proof-by-testing can never work. The counterexamples are legion.

    How about we just use a reliable algorithm that's guaranteed to work?

  • Paul Robert P. Pacheco (unregistered) in reply to Ancient_Hacker
    Ancient_Hacker:
    > How many test runs with what data sets one how many computers with how many compilers with how many different settings are needed, Ancient Hacker?

    You're playing a losing game. There is no number of tests that can "prove" a shaky bit of code.

    Not my proverb-- You might recall Dijkstra famous statement: that software testing cannot prove that there are no errors in your code; it can only demonstrate that they exist.

    Proof-by-testing can never work. The counterexamples are legion.

    How about we just use a reliable algorithm that's guaranteed to work?

  • Kuba (unregistered) in reply to Marcin
    Marcin:
    I believe the correct solution is actually to use C, and to do a binary search for the first none-zero byte before scanning that to find the high bit.

    The correct solution is to have this function in portable C as you suggest, and on x86 instead link in a whopping 4-instruction, 9-byte assembler replacement:

    .text
.globl bits
bits:
   movl 4(%esp), %eax
   bsr  %eax, %eax
   inc  %eax
   ret

    The prototype in C goes like this:

    int bits(int);

    For those insisting on it, it's possible to inline it as well (compile with -O2, this is gcc specific). Just put it into bits.h:

    static inline int bits(int val) {
   asm("bsr %0, %0\n\t"
       "inc %0"
       :"=r"(val)
       :"r"(val)
       );
   return val;
}

    This code will be placed in-line with other code, with no function call overhead, whenever the compiler is brave enough (hence -O2).

    The comments made me mostly ROTFL. You people overcomplicate so much. I bet the code runs on 32 bit x86, and there's nothing more to it than 2-5 lines of assembly. Even the binary search is simple (exercise left for the reader).

  • Me (unregistered) in reply to bstorer
    bstorer:
    Alex Papadimoulis:
    From GRG, the twelve problems with the last line ... (4) Adding a fudge factor of "1" is a kludge, which helps a bit in some cases but also overestimates the answer by one in other cases. (8) In a few instances the argument to log() isnt constrained to be positive. Taking the log of a negateive or zero is undefined and results in a run-time error. Kaboom.

    I don't see how the range can ever be negative. abs() will return a value between 0 (inclusive) and infinity (okay, okay, MAX_INT). And the addition of one is a way of avoiding taking log(0). Admittedly, it's not a good way.

    What if range==MAX_INT ? Then you roll over...

  • peachykeen (unregistered) 
    range = abs( max - min );

    The only time range is gonna be < 0 is if max < min, which totally defeats the point of "max" and "min".

  • eagle275 (unregistered) in reply to Alex Papadimoulis
    Alex Papadimoulis:
    From GRG, the twelve problems with the last line ...

    (1) Floating point numbers can't give an exact result when the numbers involved are basically transcendental and can't be represented exactly in a finite number of bits, so using the log function is basically foobar. (2) There's in FORTRAN a double-precision function "dlog" which will give better results. (3) "range" is a real number, which on most computers can't represent the full range of an integer. (4) Adding a fudge factor of "1" is a kludge, which helps a bit in some cases but also overestimates the answer by one in other cases. (5) That should be "1.0" anyway. (6) Coercing "range + 1" to real is unnecessary. (7) It should be "1.0D0" to ensure a double precision result. (8) In a few instances the argument to log() isnt constrained to be positive. Taking the log of a negateive or zero is undefined and results in a run-time error. Kaboom. (9) Dividing two inexact numbers will result in even more inexactitude. (10) Converting the result to log base two by dividing by log(2) is correct, but evaluating log base e of two will give an inexact result, as that number is transcendental. (11) And that should be "2.0" or better yet "2.0D0", or better yet, a variable holding the computed value. (12) Taking the int() of the real or double result is WRONG, as the result will sometimes be a few bits shy of the correct value. For example if you plug in "256" the answer is about 7.99981672, which when you int() it, becomes seven, which is off by one.

    Hm ... there's more to it - and the wtf starts in the articles' text.

    to represent 2022 in binary you dont need 2048 you need 2047 which is binary 11 1111 1111 (1024+512+256+128+64+32+16+8+4+2+1) 2048 is 100 0000 0000 and therefore 1 bit more than needed

Leave a comment on “Twelve on a Line”

Log In or post as a guest

Replying to comment #:

Log Out

« Return to Article