SignUtil.java

import org.web3j.crypto.Keys;
import org.web3j.crypto.Sign;
import org.web3j.utils.Numeric;

import java.security.SignatureException;

public class SignUtil {

    private static final String GETH_SIGN_PREFIX = "\u0019Ethereum Signed Message:\n32";

    /**
     * This method is expecting the signed message to be a hash of the original message. The length of the message is
     * then hardcoded to 32. Also, this might only work for messages signed by geth, not sure if other clients
     * add the prefix to the signed message.
     * @param signedHash
     * @param originalMessageHashInHex
     * @return
     * @throws SignatureException
     */
    public static String getAddressUsedToSignHashedMessage(String signedHash, String originalMessageHashInHex) throws SignatureException {
        byte[] messageHashBytes = Numeric.hexStringToByteArray(originalMessageHashInHex);
        String r = signedHash.substring(0, 66);
        String s = "0x"+signedHash.substring(66, 130);
        String v = "0x"+signedHash.substring(130, 132);
        System.out.println();
        byte[] msgBytes = new byte[GETH_SIGN_PREFIX.getBytes().length + messageHashBytes.length];
        byte[] prefixBytes = GETH_SIGN_PREFIX.getBytes();
        System.arraycopy(prefixBytes, 0, msgBytes, 0, prefixBytes.length);
        System.arraycopy(messageHashBytes, 0, msgBytes, prefixBytes.length, messageHashBytes.length);
        String pubkey = Sign.signedMessageToKey(msgBytes,
                new Sign.SignatureData(Numeric.hexStringToByteArray(v)[0],
                        Numeric.hexStringToByteArray(r),
                        Numeric.hexStringToByteArray(s)))
                .toString(16);
        System.out.println("");
        System.out.println("Pubkey: " + pubkey);
        String address = Keys.getAddress(pubkey);
        return address;
    }
}

For anyone wanting to do the same with eth.personal.sign:

    private fun verifyAddressFromSignature(address: String, signature: String): Boolean {
        val messageHashed = Hash.sha3(Hex.encodeHexString("hello world".toByteArray()))
        val messageHashBytes = Numeric.hexStringToByteArray(messageHashed)
        val signPrefix = ("\u0019Ethereum Signed Message:\n32").toByteArray()
        val r = signature.substring(0, 66)
        val s = signature.substring(66, 130)
        val v = "0x" + signature.substring(130, 132)

        val msgBytes = ByteArray(signPrefix.size + messageHashBytes.size)
        val prefixBytes = signPrefix

        System.arraycopy(prefixBytes, 0, msgBytes, 0, prefixBytes.size)
        System.arraycopy(messageHashBytes, 0, msgBytes, prefixBytes.size, messageHashBytes.size)

        val pubkey = Sign.signedMessageToKey(msgBytes,
                SignatureData(Numeric.hexStringToByteArray(v)[0],
                        Numeric.hexStringToByteArray(r),
                        Numeric.hexStringToByteArray(s)))
                .toString(16)

        val recoveredAddress = "0x" + Keys.getAddress(pubkey)
        println("address: " + recoveredAddress)


        return address == recoveredAddress
    }

It's in Kotlin but main difference is that the "0x" is removed from the s variable.

None of these solutions worked for me and it was very frustrating not finding any reasons why it didn't work. So, I started reading the Web3J code and found out that signature prefix is now changed...
From \u0019Ethereum Signed Message:\n32 to \u0019Ethereum Signed Message:\n

Working solution:

public String getAddressUsedToSignHashedPrefixedMessage(String signedHash, String originalMessageHashInHex) throws SignatureException {
        byte[] messageHashBytes = Numeric.hexStringToByteArray(originalMessageHashInHex);
        String r = signedHash.substring(0, 66);
        String s = signedHash.substring(66, 130);
        String v = "0x"+signedHash.substring(130, 132);

        byte[] msgBytes = new byte[messageHashBytes.length];
        System.arraycopy(messageHashBytes, 0, msgBytes, 0, messageHashBytes.length);

        String pubkey = Sign.signedPrefixedMessageToKey(msgBytes,
                new Sign.SignatureData(Numeric.hexStringToByteArray(v)[0],
                    Numeric.hexStringToByteArray(r),
                    Numeric.hexStringToByteArray(s)))
            .toString(16);

        log.debug("Pubkey: {}", pubkey);
        return Keys.toChecksumAddress("0x" + Keys.getAddress(pubkey));
    }

Would say the same not working - but it is not true.

1. As You see in my example I do not have 0x at the beginning of signature if you have it then do not add it to r
2. There are few types of algorithms so last 2 bytes in signature can differ eg. ..01 will be not parsed correctly 1c will be parsed correctly.
   2184bd9e841ec1ef064d32f1f05ed74bda54b6b772c4bd98a95ffbf3e83934856eb6a946c30bfe13df023a8e7a329ade1c2c0c7f7c240333ea3605e49834889e01 6ae1ee769032eaefa9d9f05d5217bf318790c10249f924b9559eb0d043f1386a3e1e39955f6d7aa5c006ed871881391be665ed37339a019c4ff2a177ec4ac3951c

Working class - good luck.

import org.apache.commons.logging.Log;
import org.apache.commons.logging.LogFactory;
import org.web3j.crypto.Keys;
import org.web3j.crypto.Sign;
import org.web3j.utils.Numeric;

import java.security.SignatureException;

public class SignUtil {

    private static final Log log = LogFactory.getLog(SignUtil.class);
    // You do not need that static values
    //private static final String GETH_SIGN_PREFIX = "\u0019Ethereum Signed Message:\n32"; //"\u0019Ethereum Signed Message:\n"
    //private static final String GETH_SIGN_PREFIX = "\u0019Ethereum Signed Message:\n";

    /**
     * This method is expecting the signed message to be a hash of the original message. The length of the message is
     * then hardcoded to 32. Also, this might only work for messages signed by geth, not sure if other clients
     * add the prefix to the signed message.
     * @param signedHash
     * @param originalMessageHashInHex
     * @return
     * @throws SignatureException
     */
    public static String getAddressUsedToSignHashedMessage(String signedHash, String originalMessageHashInHex) throws SignatureException {
        byte[] messageHashBytes = Numeric.hexStringToByteArray(originalMessageHashInHex);
        String r = "0x"+signedHash.substring(0, 64);
        String s = "0x"+signedHash.substring(64, 128);
        int iv = Integer.parseUnsignedInt(signedHash.substring(128, 130),16);
        // Version of signature should be 27 or 28, but 0 and 1 are also (!)possible
        if (iv < 27) {
            iv += 27;
        }
        String v = "0x"+ Integer.toHexString(iv);//
        log.info(v);

        byte[] msgBytes = new byte[messageHashBytes.length];
        System.arraycopy(messageHashBytes, 0, msgBytes, 0, messageHashBytes.length);

        String pubkey = Sign.signedPrefixedMessageToKey(msgBytes,
                        new Sign.SignatureData(Numeric.hexStringToByteArray(v)[0],
                                Numeric.hexStringToByteArray(r),
                                Numeric.hexStringToByteArray(s)))
                .toString(16);

        log.debug("Pubkey: " + pubkey);
        return Keys.getAddress(pubkey);
    }
}

One more cleaned-up gist to hopefully help the next person, with a runnable demo and detailed explanation: https://gist.github.com/djma/386c2dcf91fefc004b14e5044facd3a9

    /**
     * This method is the reverse of the signing process.
     * 
     * @param signedMessageInHex
     *                           The signature in hex format. It is 65 bytes long,
     *                           32 bytes for r, 32 bytes for s, and 1 byte for v.
     *                           May or may not be pre-pended with "0x".
     * @param originalMessage
     *                           The original message that was signed. Not hashed.
     * @return
     *         The address that was used to sign the message.
     * @throws SignatureException
     */
    public static String getAddressUsedToSignHashedMessage(String signedMessageInHex, String originalMessage)
            throws SignatureException {
        if (signedMessageInHex.startsWith("0x")) {
            signedMessageInHex = signedMessageInHex.substring(2);
        }

        // No need to prepend these strings with 0x because
        // Numeric.hexStringToByteArray() accepts both formats
        String r = signedMessageInHex.substring(0, 64);
        String s = signedMessageInHex.substring(64, 128);
        String v = signedMessageInHex.substring(128, 130);

        // Using Sign.signedPrefixedMessageToKey for EIP-712 compliant signatures.
        String pubkey = Sign.signedPrefixedMessageToKey(originalMessage.getBytes(),
                new Sign.SignatureData(
                        Numeric.hexStringToByteArray(v)[0],
                        Numeric.hexStringToByteArray(r),
                        Numeric.hexStringToByteArray(s)))
                .toString(16);

        return Keys.getAddress(pubkey);
    }

 public static String ecRecover(String msg, String sig) {
    byte[] signatureBytes = Numeric.hexStringToByteArray(sig);
    Sign.SignatureData signatureData = sigFromByteArray(signatureBytes);

    try {
        BigInteger recoveredKey = Sign.signedPrefixedMessageToKey(msg.getBytes(), signatureData);
        String address = "0x" + Keys.getAddress(recoveredKey);
        return address.toLowerCase();
    } catch (Exception e) {
        log.error("SignatureException, msg:{}, sig:{}, nonce:{}: ", msg, sig, nonce, e.getMessage());
    }
}

public static Sign.SignatureData sigFromByteArray(byte[] sig) {
    if (sig.length < 64 || sig.length > 65) return null;
    byte  v = sig[64];
    if (v < 27) v += 27;

    byte[] r = Arrays.copyOfRange(sig, 0, 32);
    byte[] s = Arrays.copyOfRange(sig, 32, 64);

    return new Sign.SignatureData(v, r, v);
}