-3

Is there an algorithm or a mathematical function which has the same result as the below method?

For 0 return 0

For 1...15 return 1

For 16...255 return 2

For 256...n return value doesn't matter, any number would be valid

I especially look for a one line function which can be assigned to a variable or used as a parameter. All the solutions I can think of contain more than one line or failed mathmatically (bit shifting, binary operations etc) ... For my friend jeb a multiline version of the algorithm: 

public int function(int anyInt){
 if(anyInt>15){
    return 2;
 }
 else if(anyInt>0){
    return 1;
 }
 else{ //anyInt==0 or smaller
    return 0;
 }
}

Update: Integer (calculation) based solutions are prefered.

user229044
  • 232,980
  • 40
  • 330
  • 338
Lonzak
  • 9,334
  • 5
  • 57
  • 88

3 Answers3

4

You can use a logarithm with base 16 and round up:

for (int i = 0; i <= 256; i++) {
    double x = Math.ceil(Math.log(i + 1) / Math.log(16));
    System.out.println(i + " -> " + x);
}

Output:

0 -> 0.0
1 -> 1.0
...
15 -> 1.0
16 -> 2.0
...
255 -> 2.0
256 -> 3.0
tobias_k
  • 81,265
  • 12
  • 120
  • 179
  • The OP's version will probably run faster that doing FP log and division, esp. if his input range is limited to `[0..255]` – Peter Cordes Aug 11 '15 at 11:21
  • @PeterCordes That may be, but I don't remember speed being an issue in the question... – tobias_k Aug 11 '15 at 11:32
  • right, that's why I didn't vote you down after finding the leading-zero count method, but it's still better to recommend a fast way to do something. Future SO readers will come along and grab the recommended method for their own use, not realizing that it's 10x slower than it has to be. On x86, and probably other CPUs, leading-zero count should JIT to a single integer instruction. – Peter Cordes Aug 11 '15 at 11:34
  • @PeterCordes Well, in that case, thanks a bunch for not downvoting my solution that does exactly what OP asked for. ;-) – tobias_k Aug 11 '15 at 11:53
  • not all solutions that give the correct answer are good solutions. – Peter Cordes Aug 11 '15 at 12:27
  • @PeterCordes Well, I guess what makes a "good solution" lies in the eye of the beholder. But unless speed is explicitly a concern, I prefer a solution that's easy to understand to one that's faster but hard to comprehend. Just my 2 cents. – tobias_k Aug 11 '15 at 12:38
  • @PeterCordes `not all solutions ... are good solutions`, but for some requirements there aren't good solutions at all. And in this case the bad requirement will produce bad solutions – jeb Aug 11 '15 at 12:39
  • @jeb: I don't see anything wrong with the requirements. They map pretty directly to bit-counting, which is why I think my solution makes more sense. Tobias: I think for either solution you have to stop and think it through to see that the transitions between outputs happen at the desired input boundaries. So it's not like one is "obviously right" and the other is a complicated hack. (unless you're not used to bit counting). – Peter Cordes Aug 11 '15 at 12:57
2

https://en.wikipedia.org/wiki/Binary_logarithm points out that floor(log2(i)) can be implemented in terms of leading-zeroes count.

This is available since Java5 as Integer.numberOfLeadingZeros().

Since as tobias_k points out, you want log16, divide the result by log2(16) = 4.

public static int log16(int n){
    if(n < 0) throw new IllegalArgumentException();
    return (31 - Integer.numberOfLeadingZeros(n))/4;
}

To get the rounding you need without special-casing any inputs, we start with floor(log2(n)) == 31 - lzcnt(n), and round up when doing (floor(log2(n)) + 1.0)/4.0

(31-lzcnt(n) + 4)/4 does what we want, with the rounding at the right spot.

public static int func(int n) {
    if(n < 0) throw new IllegalArgumentException();
    int r = Integer.numberOfLeadingZeros(n);
    // System.out.println("\t lzcnt(" + n + ") = " + r);
    // or use Integer.SIZE - 1 instead of 31

    return (31 - r + 4)/4;  // ceil( log2(n) + 1)/4 )
}

This gives identical results to Tobias_k's FP answer, but with only very simple integer ops.

(code modified from See How do you calculate log base 2 in Java for integers?.)

Community
  • 1
  • 1
Peter Cordes
  • 328,167
  • 45
  • 605
  • 847
  • And how do you convert `floor(log16(i))` to `ceil(log16(i))`? – tobias_k Aug 11 '15 at 11:43
  • working on an edit now, to get the rounding the OP wants. – Peter Cordes Aug 11 '15 at 11:48
  • `Math.ceil((32 - Integer.numberOfLeadingZeros(i)) / 4.)` seems to work. But that has inefficient ceil and double division again... – tobias_k Aug 11 '15 at 11:49
  • 1
    @tobias_k: don't be silly, you don't need FP math. You just need the rounding at the right step (before the divide-by-4). – Peter Cordes Aug 11 '15 at 12:20
  • @Lonzak: lzcnt / popcount (Integer.bitCount) certainly have some neat uses, and not just for bitfields. They come in handy when working with vector instructions, e.g. packed-compare -> movemask gives you a bitmap of which vector elements compared true. – Peter Cordes Aug 11 '15 at 13:51
0

You can just wrap your code into an anonymous function

int anyNumber = 17;
int result = (new Object() {public int value(int number) { if(number>15){return 2;} else if(number>0){ return 1;} else{return 1;}}}).value(anyNumber);

The problem with the requirement of one line expression is that it will produce bad/unreadable code.

More lines of codes doesn't cost anything, but prevent problems in the future.

jeb
  • 78,592
  • 17
  • 171
  • 225