Podcast #128: We chat with Kent C Dodds about why he loves React and discuss what life was like in the dark days before Git. Listen now.

Hot answers tagged

118

Computers aren't humans. A human might find it easiest to apply a divisibility rule. A computer, though, doesn't care. The simplest code would be to check n % 3 == 0. The modulo operator uses the JVM opcode irem, which is about as efficient as you can get. On an Intel CPU, irem is probably implemented using the IDIV (signed divide) instruction. On most ...


58

First off, you have nice, clean, well-formatted, easy-to-read code. You have even included comments that explain the goal of each instruction. Too much of the time I review assembly-language code, these are the things that go wrong. You've gotten them all correct. Nice job! Now I don't have to pull my hair out trying to read and understand your code. ...


46

Try int x=n>255?255:n; ... x<0?0:x ... I'd expect this to produce mov eax,n cmp eax,255 cmovgt eax,255 ; conditional mov instruction test eax,eax cmovlt eax,0 If you are using MSVC SIX, you may not get the conditional move instruction. Try switching to a modern version of visual studio.


41

Division instructions are often slow, because they have to do a conditional subtract once for each bit of the quotient. It's possible to write code which may perform better than this, but a loop which requires an iteration for each bit of the quotient isn't apt to do so. I would suggest that if a number is positive, you may start by adding the upper 11 ...


33

I guess, a really fast solution on a modern CPU looks like this: int mask = 0x2AAAAAAA; // special handling for the sign bit int diff = 2 * Integer.bitCount(x & mask) + Integer.bitCount(x & ~mask); Don't be fooled by the complicated code behind it, it's an intristic and translates to a single cycle instruction. Now we have a number between 0 and ...


29

To convert an integer to a bit string with a particular number of digits, use string.format with the b format type. For example: >>> ['{0:04b}'.format(i) for i in range(16)] ['0000', '0001', '0010', '0011', '0100', '0101', '0110', '0111', '1000', '1001', '1010', '1011', '1100', '1101', '1110', '1111'] But really it looks to me as though you don't ...


28

Here's my attempt: unsigned char clamp(int n){ int a = 255; a -= n; a >>= 31; a |= n; n >>= 31; n = ~n; n &= a; return n; } It compiles to 7 instructions - which is the same as your current version. So it may or may not be faster. I haven't timed it though. But I think these are all single-cycle instructions. ...


27

The fastest way to do this would be to align your data on 16-byte boundaries, then the entire copy just becomes 5 copies through XMM registers. This is over twice as fast as your version on my machine. Store your data like this: #include <xmmintrin.h> struct Data { union { int i[20]; __m128 v[5]; }; }; Then the copy ...


27

Yes, there is a better way: int CountOnesFromInteger(unsigned int value) { int count; for (count = 0; value != 0; count++, value &= value-1); return count; } The code relies on the fact that the expression x &= x-1; removes the rightmost bit from x that is set. We keep doing so until no more 1's are removed. This technique is described ...


19

Given how fast it should be I'd tend toward advocating a brute-force test, something like: for (int i=-100000; i<100000; i++) assertEquals(DivThreeEfficiently.isMultipleOfThree(i), i%3==0); This makes the intent more apparent, reduces the amount of code, and still covers a lot more cases than the test code you used. It would probably still be good ...


18

I wouldn't both prefixing 'internal' functions with an underscore. Instead, just put this in a module, and only export the functions you want to export. If you care about following the node style guide, you should know that node suggests ignoring Crockford's fetish for one var declaration. Note: this is pretty controversial. I'm not a fan of var ...


17

As your original implementation doesn't produce the correct results for 21, 42, 69, 81, 84, 87, and 93 (that's just from 0 to 100 !), I wanted to provide a more "common" way to handle the question of divisibility by three. This is what many humans do when they are faced with a number with a lot of digits and want to determine if it's divisible by three or ...


17

First off, Jean-François is absolutely right: you cannot assume any particular bit widths for the built-in types, short, int, long, etc. Use the types defined in stdint.h that have explicit bit widths to ensure that the code is correct and portable. Otherwise, your code looks pretty good, and this is a reasonable implementation. But… Is this a ...


17

Conditional jumps are murder on throughput due to branch-misprediction. Consider simply using a lookup-table instead: const static uint8_t map[] = { 0, 1, 2, 0, 3 }; *out = (uint8_t) ( (map[in[0]] << 0) | (map[in[1]] << 2) | (map[in[2]] << 4) | (map[in[3]] << 6)); On some architectures, shifting is more expensive ...


16

I ran some benchmarks. I included @JavaDeveloper's original code for comparison, even though it produces erroneous results. import java.util.Arrays; public class DivisibilityBenchmark { static abstract class DivPredicate { private final String name; public DivPredicate(String name) { this.name = name; } ...


16

We have a namespace called StringOperation, a class called Program, and methods called Main, ProcessInput, Shift, regions called Entry, Logic. Looking from a high level, this program could do anything, as these terms are completely meaningless. Strive to find more meaningful names for your program elements, so that readers can have a clue what the program ...


15

You have added public GemCounter() { // default constructor. Does nothing. } which is not needed for the program to work because, The compiler automatically provides a no-argument, default constructor for any class without constructors. This default constructor will call the no-argument constructor of the superclass. In this situation, the ...


15

Here are some things that may help you improve your code. Understand type implications The code includes a bitFlag array that is declared as const int8_t but then contains a value that is 0x80. The problem with that is that when the compiler encounters the constant 0x80, it converts it into an int by default, and so that would be the value 128. However, ...


14

Conclusion 2011-12-05: I tried all of the suggestions again with VS 2010 Express. The generated code didn't change much, but the register assignments did which affected the overall results. A slight modification of the straightforward implementation suggested by Ira Baxter came up the winner. inline BYTE Clamp(int n) { n = n>255 ? 255 : n; ...


14

I think using Regex will be too much for this little task. A simple split by 1s should suffice. public static int ComputeLargestBinaryGap2(int value) { return Convert // convert to binary .ToString(value, 2) // remove leading and trailing 0s, as per requirement .Trim('0') // split the string by ...


14

Unless you wish to optimize the code, with specialized swappers for various hosts orders, you are doing it wrong. I invite you to check The Byte Order Fallacy by Rob Pike. The punch line: the byte order of the computer you are executing the code on doesn't matter, because the language abstracts it for you. Thus, only the byte order of the network matters, ...


13

I do, however insist on making everything explicit. I'm not a huge fan of implicit anything... Maybe that's something I need to get over? No, that is very good practice and a good habit. Particularly, there are many dangerous, implicit type promotions going on in C, that explicit type casts can prevent. However, if you want to be explicit, you must ...


13

Logic Never omit the optional braces like that. Think of yourself as a contributing factor to a future coding accident. If you really want to omit braces, then put the statement on the same line, so that there is no possibility of misinterpretation. The function does not check for overlong encodings, invalid byte sequences, or invalid code points. Those ...


13

Not much to say. Logical operators used a bit inconsistently: gotElement |= 1 << element; gemsSoFar = gemsSoFar & gotElement; better use &= in the second line, or spell out the first. gotElement is somewhat unclear. rockElements, maybe? In real life I'd also oppose extensive comments.


13

Division and multiplication are relatively computationally costly operations compared to shifts and AND operations. Try to reformulate your answer in terms of >> and & and you will likely find a performance gain. Other things I noticed that may help you improve your program: Eliminate unused variables Both len and str are unused and may be ...


13

Layout Put your main method on the top, since it tells main purpose of the application. And, C# isn't like C++, you don't have to define the method ahead, before calling them. class Program { uint bitSize, shiftCount, mask, partionSize; static void Main(string[] args); void setValue(ref uint var, uint k, uint i, uint val); uint getValue(...


12

That global array is indeed not good. You'll need to pass around an array, but you shouldn't do it with a C-style array. Doing that will cause it to decay to a pointer, which you should avoid in C++. If you have C++11, you could use std::array, which will be set at an initial size. But if you don't have C++11, and also want to adjust the size, use an std:...


12

Your bitwise operations are fine, though the >>> right-shifts are unnecessary. @Lucien and @Corbin are right! The right-shift operators prevent (128 << 24) from being interpreted as a negative number. The rest of the code is fine too, but a bit long for my taste. Personally, I'd use a long regular expression to do all the parsing and ...


12

Your question comes in multiple parts: General code review, adding algorithms, and then performance relative to standard BigInteger General Review Let's focus on this method, it shows essentially all the general issues I see: public static BigInteger add(BigInteger x, BigInteger y) { boolean A, B, carry=false; BigInteger sum=BigInteger.ZERO; int ...


12

It's not a bad solution. It's not immediately obvious what processRock() function does, so I would just make some minor adjustments in the way the problem is decomposed and in naming, for clarity. private static final String ALL_ELEMENTS = "abcdefghijklmnopqrstuvwxyz"; private int commonElements = bitsOfRock(ALL_ELEMENTS); private static int bitsOfRock(...


Only top voted, non community-wiki answers of a minimum length are eligible