# Tag Info

122

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 ...

60

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. ...

42

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 ...

34

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 ...

28

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 ...

19

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 ...

18

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 good way to ...

17

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; ...

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

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)); There are many architectures where shifting is more ...

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

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 ...

15

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, ...

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

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(...

14

If you really care about performance you may also give a chance to a branchless version. Note that compiler may optimize code with explicit branches (if and ?:) if target architecture supports CMOV (& similar) instructions, check generated assembly output. In these examples I will use X86 mnemonics but I suppose meaning is clear whichever your ...

14

The current implementation Your implementation is correct, and takes $O(n)$ time, where $n$ is the number of bits in an int. One thing you can improve is the initial setting of b_mask. Currently, you use a loop, but it can be done like this: unsigned int b_mask = 1u << (sizeof(b_mask)*CHAR_BIT - 1); Actually, there are two other strategies you ...

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

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 ...

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

Loop invariants code motion This is the name of an optimization performed by most compilers: when they detect code that actually does not depend on the state of the loop, they move it out of the loop. It's not as obvious as the usual invariants, but let's have a look at this line: Unsigned res_i = (lhs_p_cpy & rhs_p_cpy) ^ lhs_i ^ rhs_i; lhs_i and ...

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

Java has Integer.highestOneBit that can make this a bit simpler: int highestOneBit = Integer.highestOneBit(value); if (value == highestOneBit) { return value; } return highestOneBit << 1;

13

The beginning of your program obviously should be following the "HINT" and using xor instead of add. This is some really wacky code: ror eax, 0x1 ; Rotate the lowest bit out of the register. So that the carry-flag gets a new state. jc evenNumber ; jc == Jump if the carry-flag has become 1. Means the last bit has ...

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 ...

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