3 ms·

http://pastie.caboo.se/113312 http://pastie.caboo.se/113312

by tmm1 19y ago

dhouston 19y ago
float precision issues make me nervous (although it's probably ok here), not to mention log() is kind of expensive compared to bit shifting why not just something like def fn(n): ret=1; while ret < n: ret <<= 1; return ret (news.yc/browsers mangle whitespace; proper formatting is left as an exercise to the reader)
- Goladus 19y ago
  To format code, add a whole bunch of returns and then indent 4-5 spaces (5 returns and 6 spaces later whitespace does what I want) I think it's supposed to be 4 and 4, but I had some issues once and since then I just pile on returns and spaces until I get bored.
  - nostrademons 19y ago
    I thought it's 2 and 1: print 'Hello world' Yup, that's it. A blank line before the indented block, then any amount of indentation. Reddit is 2 and 4.
gojomo 19y ago
You could use that approach in Java... public int roundUpToPowerOfTwo(int i) { return 1 << (int)(Math.ceil(Math.log(i)/Math.log(2))); } ...but the first approach that occurred to this Java coder was instead... public int roundUpToPowerOfTwo(int i) { int rounded = 1; while(rounded<i) rounded <<= 1; return rounded; }
tallpapab 19y ago
You have an infinite loop when i < 2^30. static int nextOne(int theInt) { int answer = 1; while (answer < theInt && 0 < answer) { answer <<= 1; } if (answer < 1) { throw new IllegalArgumentException("Sorry, " + theInt + " is bigger than 2 to the power of 30 (1073741824)."); } return answer; }
- gojomo 19y ago
  Good point. (And, as your signature indicates, this is more likely to be a static utility method.) If I were defensively programming against unanswerable input, I'd tend towards failing fast with a single early check: static int roundUpToPowerOfTwo(int i) { if(i>(1<<30)) throw new IllegalArgumentException("Answer overflows int"); int rounded = 1; while(rounded<i) rounded <<= 1; return rounded; } If we needed to give answers for any size integer (or at least up to 2^(2^31-1)), we could use BigInteger, whose #bitLength method is useful: static BigInteger roundUpToPowerOfTwo(BigInteger i) { return BigInteger.ONE.shiftLeft(i.subtract(BigInteger.ONE).bitLength()); } And if we weren't being literal-minded about the original request, it might make sense to just return the exponent rather than the power-of-2 itself, and let the caller worry about overflows: static int ceilLog2(long val) { return BigInteger.valueOf(val-1).bitLength(); } Of course we are ignoring negative exponents, in the integer spirit of the original question. There, is it done to death yet? :)

http://pastie.caboo.se/113312 http://pastie.caboo.se/113312

by tmm1 19y ago

http://pastie.caboo.se/113312 http://pastie.caboo.se/113312

float precision issues make me nervous (although it's probably ok here), not to mention log() is kind of expensive compared to bit shifting why not just something like def fn(n): ret=1; while ret < n: ret <<= 1; return ret (news.yc/browsers mangle whitespace; proper formatting is left as an exercise to the reader)

Goladus 19y ago
To format code, add a whole bunch of returns and then indent 4-5 spaces (5 returns and 6 spaces later whitespace does what I want) I think it's supposed to be 4 and 4, but I had some issues once and since then I just pile on returns and spaces until I get bored.
- nostrademons 19y ago
  I thought it's 2 and 1: print 'Hello world' Yup, that's it. A blank line before the indented block, then any amount of indentation. Reddit is 2 and 4.

gojomo 19y ago

You could use that approach in Java... public int roundUpToPowerOfTwo(int i) { return 1 << (int)(Math.ceil(Math.log(i)/Math.log(2))); } ...but the first approach that occurred to this Java coder was instead... public int roundUpToPowerOfTwo(int i) { int rounded = 1; while(rounded<i) rounded <<= 1; return rounded; }

tallpapab 19y ago

You have an infinite loop when i < 2^30. static int nextOne(int theInt) { int answer = 1; while (answer < theInt && 0 < answer) { answer <<= 1; } if (answer < 1) { throw new IllegalArgumentException("Sorry, " + theInt + " is bigger than 2 to the power of 30 (1073741824)."); } return answer; }

gojomo 19y ago
Good point. (And, as your signature indicates, this is more likely to be a static utility method.) If I were defensively programming against unanswerable input, I'd tend towards failing fast with a single early check: static int roundUpToPowerOfTwo(int i) { if(i>(1<<30)) throw new IllegalArgumentException("Answer overflows int"); int rounded = 1; while(rounded<i) rounded <<= 1; return rounded; } If we needed to give answers for any size integer (or at least up to 2^(2^31-1)), we could use BigInteger, whose #bitLength method is useful: static BigInteger roundUpToPowerOfTwo(BigInteger i) { return BigInteger.ONE.shiftLeft(i.subtract(BigInteger.ONE).bitLength()); } And if we weren't being literal-minded about the original request, it might make sense to just return the exponent rather than the power-of-2 itself, and let the caller worry about overflows: static int ceilLog2(long val) { return BigInteger.valueOf(val-1).bitLength(); } Of course we are ignoring negative exponents, in the integer spirit of the original question. There, is it done to death yet? :)