Convert int to Hex String without using Integer.toHexString();

Question

Following is the problem statement from LeetCode.

Given an integer, write an algorithm to convert it to hexadecimal. For negative integer, two’s complement method is used.

Note:

All letters in hexadecimal (a-f) must be in lowercase.

The hexadecimal string must not contain extra leading 0s. If the number is zero, it is represented by a single zero character '0'; otherwise, the first character in the hexadecimal string will not be the zero character.

The given number is guaranteed to fit within the range of a 32-bit signed integer.

You must not use any method provided by the library which converts/formats the number to hex directly.

Here's my solution:

public class Solution {
    private static final String characters = "0123456789abcdef";
    private static final char[] digits = characters.toCharArray(); 
    
    private Stack<Integer> stack = new Stack<>();
    public String toHex(int num) {
        if (num == 0) return "0";
        
        stack.clear();
        while (num != 0) {
            stack.push(getDigit(num));
            num = num >>> 4;
            System.out.println(num);
            if (stack.size() > 8) break;
        }
        
        StringBuilder buffer = new StringBuilder();
        while (!stack.empty()) {
            buffer.append(digits[stack.pop()]);
        }
        
        return buffer.toString();
    }
    
    private int getDigit(int num) {
        int result = num & 0xF;
        return result;
    }
}

The problem is that this solution works, but it's not very performant--I'm in the bottom 1% of runtimes with this solution. I'm wondering if my use of the Stack Object or the StringBuilder is causing me grief.

It's also totally possible that a ton of submissions are ignoring the restriction and using the Java APIs anyway. :) But I figured I'd post here and learn how I could make this more efficient.

You could initialize StringBuilder with a big size. It will save you a lot of redundant copying of the char [ ] (the array in StringBuilder) when it is full — denvercoder9
– denvercoder9, Commented Oct 29, 2016 at 19:24
Some java experts can take one look at this code and tell you what is taking longer than it should. The rest of us need to use a profiler. I'm not sure how much, if any overhead, the Stack implementation imposes. Also, the variance in timing and the nature of Java may mean that the next time you run your code it only take 10ms. — President James K. Polk
– President James K. Polk, Commented Oct 29, 2016 at 19:27
Try removing the System.out.println() you currently have within the loop. That probably contributes significantly to the execution time. — Mick Mnemonic
– Mick Mnemonic, Commented Oct 29, 2016 at 20:28
@Marvin thanks, didn't realize that site was available. I'll give it a try next time. — Vishal Kotcherlakota
– Vishal Kotcherlakota, Commented Oct 30, 2016 at 3:32

Adam Rice · Accepted Answer · 2016-10-29 22:11:16Z

3

I managed a small improvement with just a few tweaks to your code.

I've shaved 8ms off the run time moving it up to beating 51.90% of the other solutions.

public class Solution {
    private static final char[] digits = "0123456789abcdef".toCharArray(); 

    private Stack<Integer> stack = new Stack<>();
    public String toHex(int num) {
        if (num == 0) return "0";

        stack.clear();
        while (num != 0) {
            stack.push(num & 0xF);
            num = num >>> 4;
            if (stack.size() > 8) break;
        }

        StringBuilder buffer = new StringBuilder();
        while (!stack.empty()) {
            buffer.append(digits[stack.pop()]);
        }

        return buffer.toString();
    }
}

Firstly, I changed the way the digits array is constructed, condensing the two original lines into one.

I also deleted the System.out.println call.

Finally, I replaced the call to the getDigit() method with its contents inlined in the main code.

* UPDATE *

This is also a cleaner option, reducing the number of loops to one and removing the need to use a Stack.

public class Solution {
    private static final char[] digits = "0123456789abcdef".toCharArray(); 

    public String toHex(int num) {
        if (num == 0) return "0";

        StringBuilder buffer = new StringBuilder();
        while (num != 0) {
            buffer.append(digits[num & 0xF]);
            num = num >>> 4;
        }
        return buffer.reverse().toString();
    }
}

Note: Performance of this seems to fluctuate between 7ms and 8ms.

edited Oct 29, 2016 at 22:11

answered Oct 29, 2016 at 21:09

Adam Rice

8908 silver badges21 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Vishal Kotcherlakota Over a year ago

I totally overlooked the println call...thanks! Nice call on the reverse--good to know that the stringbuilder has that capability.

Bohemian · Accepted Answer · 2016-10-30 09:02:11Z

2

Do less by making these changes:

Lose the stack. It's convenient, but relatively heavy considering this is "math" task
Don't use char[], use byte[] for the output chars '0' through 'f'. All chars are < 127 so byte is enough. It also means you can use the deprecated but fast and ideal constructor public String(byte[] ascii, int hibyte, int offset, int count)
save your result in a byte[8]
capture all 8 4-bit nybbles. If nybble[i] is non-zero, put output byte at the index of the nybble in the result at index i. If it's the first non-zero, remember i and use it as offset
call the previously mentioned constructor using 0 for hibyte and 8 - start as count

edited Oct 30, 2016 at 9:02

answered Oct 30, 2016 at 5:14

Bohemian♦

427k103 gold badges604 silver badges750 bronze badges

Collectives™ on Stack Overflow

Convert int to Hex String without using Integer.toHexString();

2 Answers 2

1 Comment

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related