Timeline for Efficiently checking if a number is divisible by 3
Current License: CC BY-SA 3.0
17 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 8, 2017 at 16:23 | history | edited | maaartinus | CC BY-SA 3.0 |
added 158 characters in body
|
| Mar 30, 2015 at 5:37 | comment | added | k_g |
@maaartinus I remember when I was first programming and got an error with trying to input the number 019 it drove me crazy for hours before I realized that a leading 0 meant something. I suppose it was better than if I'd used 012 somewhere in my code though :-)
|
|
| Jun 10, 2014 at 4:06 | history | bounty awarded | 200_success | ||
| Jun 4, 2014 at 18:28 | comment | added | maaartinus | @jwg Note that addition is way more complicated and could be implemented via a loop, too. I'm sure, POPCNT is a 1 cycle instruction, but there seems to be some limitation (like this one) preventing my alg from being faster than the more complicated on by supercat. | |
| Jun 4, 2014 at 13:20 | comment | added | jwg |
bitCount seems like it should be a costly operation (if it was implemented with a loop similarly to the OP's loop), is it made much quicker in hardware?
|
|
| Jun 4, 2014 at 6:50 | comment | added | Taemyr | @maaartinus Thanks. For some reason I was thinking different from zero rather than less than zero. | |
| Jun 4, 2014 at 6:32 | comment | added | maaartinus |
@Taemyr They aren't and I don't care... a number is negative IFF its most significant bit is set. That's all I need. I could have written ((TABLE << diff) & 0x8000_0000_0000_0000L) != 0 instead, it's equivalent, but way longer and possibly also a bit slower. Note that I was wrong with using int.
|
|
| Jun 4, 2014 at 6:21 | comment | added | Taemyr | @maaartinus After you have shiftet the relevant bit into the 31st position how you know that all the other bits are 0? | |
| Jun 3, 2014 at 19:58 | history | edited | maaartinus | CC BY-SA 3.0 |
added 603 characters in body
|
| Jun 3, 2014 at 19:26 | comment | added | maaartinus |
@supercat I guess so. But I hate octal, the current notation is totally brain damaged (I'd propose the 0o prefix). I must confess that I generated the constant (by trying a few multiples of 3) and never looked at the value. But logically, every third bit is set.
|
|
| Jun 3, 2014 at 18:15 | comment | added | supercat |
That TABLE looks like one of the few places where octal notation might actually be useful. I think octal notation should have used something like 0q rather than a naked leading 0, but 01111111111111111111111L is a cute constant, isn't it?
|
|
| Jun 3, 2014 at 16:28 | history | edited | maaartinus | CC BY-SA 3.0 |
added 100 characters in body
|
| Jun 3, 2014 at 16:09 | history | edited | maaartinus | CC BY-SA 3.0 |
added 241 characters in body
|
| Jun 3, 2014 at 15:36 | comment | added | maaartinus | @Taemyr I'm not getting your last sentence. The left shift shifts the relevant bit into the 31st position so I can test the sign. | |
| Jun 3, 2014 at 15:34 | history | edited | maaartinus | CC BY-SA 3.0 |
added 692 characters in body
|
| Jun 3, 2014 at 7:22 | comment | added | Taemyr | Some explanation of why this works would be in order. (Ie. why the digit sum test for divisibility by 3 in binary is the same as for 11 in decimal). And also why the offset of 1 in two complements means that treating the sign bit as an even indexed bit yields the correct result. Finaly your return statement seems to return true if any diff higher than the current divides 3 - I think you need to catch only the least bit. | |
| Jun 3, 2014 at 4:34 | history | answered | maaartinus | CC BY-SA 3.0 |