原码补码

References

Java 实现 AirflowDagFileLocHash

package com.sensetime.airflow.sidecar.util;

import org.apache.commons.codec.digest.DigestUtils;

import java.math.BigInteger;
import java.nio.charset.StandardCharsets;
import java.util.Arrays;

/**
 * @author zhangqiang
 * @since 2021/1/15 15:17
 */
public class CommonUtil {

    /**
     * Byte Array to HexString
     * 
     * 在对字节数组高低位拼接时,需要先移位再与或,比如拼接一个 int 类型的数,对`byte[] b = new byte[4]`处理的过程就是
     * 对每个 byte b[i] 转换成 int,然后进行移位操作,最后执行与或操作进行高低位拼接。这个过程中需要保证 byte -> int 
     * 的补码不能发生变化。
     *
     * `b[i] & 0xff` 的含义:
     *   1. 只取低 8 位
     *   2. 保持补码的一致性,不会因为 JVM 的补位操作导致补码发生变化,哪怕补位后的补码和补位前的补码表示是相同原码
     *     
     * 计算机中都是用补码表示数值,正数的补码是原码,而负数的补码是反码加 1,假设`b[0]=-12`,原码表示为`1000 1100`,
     * 反码为`1111 0011`,补码为`1111 0100`,当 byte -> int 就由 8 位变成 32 位,JVM 会做一个补位处理,补位是补 1 
     * 还是补 0,取决于 byte 的最高位是 1 还是 0,`1111 0100`高位是 1,为了保证补位后数值不变高位补 1,补位后变成
     * `1111 1111 1111 1111 1111 1111 1111 0100`,
     * `1111 1111 1111 1111 1111 1111 1111 0100` - 1 = 
     * `1111 1111 1111 1111 1111 1111 1111 0011`,最高位不变按位取反
     * `1000 0000 0000 0000 0000 0000 0000 1100` = -12,虽然这两个的补码不同,但是代表的原码都是 -12。
     *
     * 当我们进行高位拼接时,需要对补码进行移位再与或。如果使用由 JVM 补位后的补码,移位后与或计算的结果就是错误的,我们需要
     * 保证`byte -> int`后的补码不能发生任何变化,也就是保证前后的补码的一致性
     *
     * `0xff`在 32 位情况下表示为
     * `0000 0000 0000 0000 0000 0000 1111 1111`
     * `1111 1111 1111 1111 1111 1111 1111 0100`,与 -12 的补码做`&`操作后得出
     * `0000 0000 0000 0000 0000 0000 1111 0100`,只保留低八位,这样前后两次的补码就一致了。byte[0]是高 8 位,左移 24 位
     * `1111 0100 0000 0000 0000 0000 0000 0000`
     *
     * 假设`b[1]=-12`,左移位 16 位后得到
     * `0000 0000 1111 0100 0000 0000 0000 0000`,与高 8 位
     * `1111 0100 0000 0000 0000 0000 0000 0000`执行与或进行拼接得到
     * `1111 0100 1111 0100 0000 0000 0000 0000`,后面的以此类推
     *
     * @param b
     * @return
     */
    public static String byteArrayToHexString(byte[] b) {
        StringBuilder result = new StringBuilder();
        for (int i = 0; i < b.length; i++) {
            result.append(Integer.toString((b[i] & 0xff) + 0x100, 16).substring(1));
        }
        return result.toString();
    }

    /**
     * Python 的 Java 实现
     *
     * <code>
     * * import hashlib
     * *
     * * def dag_fileloc_hash(full_filepath: str) -> int:
     * *    """Hashing file location for indexing.
     * *
     * *    :param full_filepath: full filepath of DAG file
     * *    :return: hashed full_filepath
     * *    """
     * *    # Only 7 bytes because MySQL BigInteger can hold only 8 bytes (signed).
     * *    # '>Q' 表示按高位字节序解析成 unsigned long long
     * *    return struct.unpack('>Q', hashlib.sha1(full_filepath.encode('utf-8')).digest()[-8:])[0] >> 8
     * </code>
     *
     * <p>
     * 在计算机系统中,数值一律用补码来表示(存储)。 主要原因:使用补码,可以将符号位和其它位统一处理;同时,
     * 减法也可按加法来处理。
     * <li>
     * 机器数:一个数在计算机中的二进制表示形式, 叫做这个数的机器数。机器数是带符号的,在计算机用一个数的最高位
     * 存放符号, 正数为 0, 负数为 1.
     * <li>
     * 真值:因为第一位是符号位,所以机器数的形式值就不等于真正的数值。例如有符号数 10000011,其最高位 1 代表负,
     * 其真正数值是 -3 而不是形式值 131(10000011 转换成十进制等于 131)。所以,为区别起见,将带符号位的机器数
     * 对应的真正数值称为机器数的真值。
     * <li>
     * 原码:原码就是符号位加上真值的绝对值, 即用第一位表示符号, 其余位表示值.
     * <li>
     * 反码:反码的表示方法是:正数的反码是其本身,负数的反码是在其原码的基础上, 符号位不变,其余各个位取反.
     * <li>
     * 补码:补码的表示方法是:正数的补码就是其本身,负数的补码是在其原码的基础上, 符号位不变, 其余各位取反,
     * 最后 +1 (即在反码的基础上 +1),或者负数绝对值原码按位取反。
     *
     * <p>
     * 在 Java 中,是采用补码来表示数据的,但是由于 Java byte 的范围是 [-128, 127],而无符号 byte 应该是 
     * [0, 255],Java 没有无符号类型,所以对于 128+ 的数会变成负数,比如 244 会变成 -12,128 会变成 -128,
     * BigInteger 可以有无限多个 bit,它按 big-endian 字节序去解析 byte[],即 byte[0] 代表高 8 位,依次类
     * 推,当你的补码数组的第一个字节本应是 128,在 Java 用 byte 表示会变成 -128,本来是个正整数,现在被误认
     * 为负的了,导致错误的解析,正常可以用 int a = ((byte) 128) & 0xff 解决这个问题。
     * 在 {@link BigInteger#BigInteger(int, byte[])},第一个参数 signum 代表改对象的符号,signum = 1,
     * 代表当前的数应该是个正数,-1 代表是负数,0 就是 0 这样 BigInteger 就能正确的解析当前的数了。
     *
     * @param fileLoc
     * @return
     */
    public static BigInteger airflowDagFileLocHash(String fileLoc) {
        byte[] strBytes = fileLoc.getBytes(StandardCharsets.UTF_8);
        byte[] sha1DigestBytes = DigestUtils.sha1(strBytes);
        byte[] cBytes = Arrays.copyOfRange(sha1DigestBytes,
                sha1DigestBytes.length - 8, sha1DigestBytes.length);
        return new BigInteger(1, cBytes).shiftRight(8);
    }

}

qin

取消

感谢您的支持,我会继续努力的!

扫码支持
扫码支持
扫码打赏

打开支付宝扫一扫,即可进行扫码打赏哦