Mapowanie dwóch liczb całkowitych do jednej w unikalny i deterministyczny sposób


235

Wyobraź sobie dwie dodatnie liczby całkowite A i B. Chcę połączyć te dwie w jedną liczbę całkowitą C.

Nie może być innych liczb całkowitych D i E, które łączą się z C. Tak więc łączenie ich z operatorem dodawania nie działa. Np. 30 + 10 = 40 = 40 + 0 = 39 + 1 Nie działa też konkatynacja. Np. „31” + „2” = 312 = „3” + „12”

Ta kombinacja operacji powinna również być deterministyczna (zawsze dawać ten sam wynik przy tych samych danych wejściowych) i zawsze powinna dawać liczbę całkowitą po stronie dodatniej lub ujemnej liczb całkowitych.


10
Powinieneś wyjaśnić, czy masz na myśli liczby całkowite w oprogramowaniu czy liczby całkowite z matematyki. W oprogramowaniu wybierasz dowolny typ liczb całkowitych, który będzie miał rozmiar, więc masz ich skończoną liczbę, więc nie ma rozwiązania (chyba, że ​​oczywiście twoje dane wejściowe są w pewnym zakresie, a wyniki mogą być dowolna liczba całkowita). W matematyce zobacz rozwiązanie ASk.
Daniel Daranas

Mówię o ograniczonych liczbach całkowitych w niskim, dodatnim zakresie. Powiedz 0 do 10 000
zaszkodzi

27
@harm: A co powiesz na sprawiedliwy 10,001*A + B?
BlueRaja - Danny Pflughoeft

2
Znalazłem te funkcje PHP: gist.github.com/hannesl/8031402
cakan

Jeśli kolejność nie ma znaczenia, np .: (3,12) i (12,3) dają ten sam wynik, używam „A + B” + „A * B”
Sodj

Odpowiedzi:


233

Szukasz NxN -> Nmapowania bijective . Służą one np . Dovetailing . Zapoznaj się z tym plikiem PDF, aby uzyskać wprowadzenie do tak zwanych funkcji parowania . Wikipedia wprowadza określoną funkcję parowania, a mianowicie funkcję parowania Cantor :

pi (k1, k2) = 1/2 (k1 + k2) (k1 + k2 + 1) + k2

Trzy uwagi:

  • Jak wyjaśnili inni, jeśli planujesz zaimplementować funkcję parowania, może wkrótce okazać się, że potrzebujesz dowolnie dużych liczb całkowitych (bignów).
  • Jeśli nie chcesz rozróżniać par (a, b) i (b, a), posortuj aib przed zastosowaniem funkcji parowania.
  • Właściwie to skłamałem. Szukasz ZxZ -> Nmapowania bijective . Funkcja Cantora działa tylko na liczbach nieujemnych. Nie stanowi to jednak problemu, ponieważ łatwo zdefiniować bijection f : Z -> N, tak jak poniżej :
    • f (n) = n * 2, jeśli n> = 0
    • f (n) = -n * 2-1, jeśli n <0

13
+1 Myślę, że to poprawna odpowiedź na nieograniczone liczby całkowite.
Nieznany

4
Jak mogę uzyskać ponownie wartość k1, k2?
MinuMaster,

3
@MinuMaster: opisany w tym samym artykule w Wikipedii, w części Odwracanie funkcji parowania Cantor .
Stephan202

4
Zobacz także funkcję Szudzika, wyjaśnioną przez newfal poniżej.
OliJG

1
Chociaż jest to poprawne dla nieograniczonych liczb całkowitych, nie jest najlepsze dla ograniczonych liczb całkowitych. Myślę, że komentarz @ blue-raja jest jak dotąd najbardziej sensowny.
Kardasis

226

Funkcja parowania kantora jest naprawdę jedną z lepszych, ponieważ jest prosta, szybka i zajmuje mało miejsca, ale jest coś jeszcze lepiej opublikowanego w Wolfram przez Matthew Szudzika tutaj . Ograniczeniem funkcji parowania Cantora (względnie) jest to, że zakres zakodowanych wyników nie zawsze mieści się w granicach 2Nbitowej liczby całkowitej, jeśli dane wejściowe są dwiema Nliczbami całkowitymi. Oznacza to, że jeśli moje dane wejściowe są 16liczbami całkowitymi od dwóch bitów 0 to 2^16 -1, to możliwe są 2^16 * (2^16 -1)kombinacje danych wejściowych, więc zgodnie z oczywistą zasadą Pigeonhole potrzebujemy wyjścia o wielkości co najmniej 2^16 * (2^16 -1)równej 2^32 - 2^16lub innymi słowy mapie32idealnie powinny być możliwe liczby bitowe. To może nie mieć praktycznego znaczenia w świecie programowania.

Funkcja parowania kantora :

(a + b) * (a + b + 1) / 2 + a; where a, b >= 0

Odwzorowanie dla dwóch maksymalnie 16-bitowych liczb całkowitych (65535, 65535) będzie wynosić 8589803520, który, jak widać, nie mieści się w 32 bitach.

Wejdź w funkcję Szudzika :

a >= b ? a * a + a + b : a + b * b;  where a, b >= 0

Mapowanie dla (65535, 65535) będzie teraz 4294967295, co jak widać jest liczbą całkowitą 32-bitową (od 0 do 2 ^ 32 -1). Właśnie tam to rozwiązanie jest idealne, po prostu wykorzystuje każdy punkt w tej przestrzeni, więc nic nie może zapewnić więcej miejsca.


Teraz, biorąc pod uwagę fakt, że zwykle mamy do czynienia z podpisanymi implementacjami liczb o różnych rozmiarach w językach / frameworkach, rozważmy signed 16liczby całkowite od - -(2^15) to 2^15 -1(później zobaczymy, jak rozszerzyć nawet wyjście do zakresu ponad podpisany zakres). Od ai bmuszą być pozytywne, różnią się od 0 to 2^15 - 1.

Funkcja parowania kantora :

Odwzorowanie dla dwóch maksymalnie 16-bitowych liczb całkowitych ze znakiem (32767, 32767) będzie wynosić 2147418112, czyli niewiele więcej niż maksymalna wartość dla 32-bitowej liczby całkowitej ze znakiem.

Teraz funkcja Szudzika :

(32767, 32767) => 1073741823, znacznie mniejszy ..

Rozważmy liczby całkowite ujemne. To jest poza pierwotnym pytaniem, które znam, ale po prostu opracowaniem, aby pomóc przyszłym użytkownikom.

Funkcja parowania kantora :

A = a >= 0 ? 2 * a : -2 * a - 1;
B = b >= 0 ? 2 * b : -2 * b - 1;
(A + B) * (A + B + 1) / 2 + A;

(-32768, -32768) => 8589803520, który jest Int64. 64-bitowy sygnał wyjściowy dla 16-bitowych sygnałów wejściowych może być tak nieprzebaczalny !!

Funkcja Szudzika :

A = a >= 0 ? 2 * a : -2 * a - 1;
B = b >= 0 ? 2 * b : -2 * b - 1;
A >= B ? A * A + A + B : A + B * B;

(-32768, -32768) => 4294967295, który jest 32-bitowy dla zakresu bez znaku lub 64-bitowy dla zakresu ze znakiem, ale wciąż lepszy.

Wszystko to, podczas gdy wyniki zawsze były pozytywne. W podpisanym świecie zaoszczędzenie miejsca zajmowałoby jeszcze więcej, gdybyśmy mogli przenieść połowę mocy wyjściowej na oś ujemną . Możesz to zrobić w ten sposób dla Szudzika:

A = a >= 0 ? 2 * a : -2 * a - 1;
B = b >= 0 ? 2 * b : -2 * b - 1;
C = (A >= B ? A * A + A + B : A + B * B) / 2;
a < 0 && b < 0 || a >= 0 && b >= 0 ? C : -C - 1;

(-32768, 32767) => -2147483648

(32767, -32768) => -2147450880

(0, 0) => 0 

(32767, 32767) => 2147418112

(-32768, -32768) => 2147483647

Co robię: po nałożeniu ciężaru 2na dane wejściowe i przejściu przez funkcję dzielę wyjście przez dwa i przenoszę niektóre z nich na oś ujemną, mnożąc przez -1.

Zobacz wyniki, dla dowolnego wejścia w zakresie liczby 16bitów ze znakiem , wyjście leży w granicach 32fajnej liczby całkowitej ze znakiem . Nie jestem pewien, jak postąpić w ten sam sposób dla funkcji parowania Cantor, ale nie próbowałem tyle, ile nie jest tak wydajna. Co więcej, więcej obliczeń związanych z funkcją parowania Cantora oznacza również jego spowolnienie .

Oto implementacja C #.

public static long PerfectlyHashThem(int a, int b)
{
    var A = (ulong)(a >= 0 ? 2 * (long)a : -2 * (long)a - 1);
    var B = (ulong)(b >= 0 ? 2 * (long)b : -2 * (long)b - 1);
    var C = (long)((A >= B ? A * A + A + B : A + B * B) / 2);
    return a < 0 && b < 0 || a >= 0 && b >= 0 ? C : -C - 1;
}

public static int PerfectlyHashThem(short a, short b)
{
    var A = (uint)(a >= 0 ? 2 * a : -2 * a - 1);
    var B = (uint)(b >= 0 ? 2 * b : -2 * b - 1);
    var C = (int)((A >= B ? A * A + A + B : A + B * B) / 2);
    return a < 0 && b < 0 || a >= 0 && b >= 0 ? C : -C - 1;
}

Ponieważ obliczenia pośrednie mogą przekraczać limity liczby 2Ncałkowitej ze znakiem, użyłem 4Ntypu liczby całkowitej (ostatni podział przez 2powoduje powrót wyniku 2N).

Link, który podałem w alternatywnym rozwiązaniu, ładnie przedstawia wykres funkcji wykorzystującej każdy pojedynczy punkt w przestrzeni. To niesamowite, że możesz jednoznacznie zakodować parę współrzędnych w pojedynczą liczbę w sposób odwracalny! Magiczny świat liczb !!


5
Jaka byłaby zmodyfikowana funkcja odblokowywania dla podpisanych liczb całkowitych?
Arets Paeglis,

7
Ta odpowiedź mnie myli. Jeśli chcesz mapować (0,0)thru (65535,65535)do jednego numeru, a następnie a<<16 + bjest lepszy w zasadzie każdy sposób (szybsze, prostsze, łatwiejsze do zrozumienia, bardziej oczywiste) . Jeśli chcesz (-32768,-32768), aby (327687,327687)zamiast tego po prostu przedmiotem 32768 pierwszy.
BlueRaja - Danny Pflughoeft

2
@ BlueRaja-DannyPflughoeft masz rację. Moja odpowiedź byłaby ważna, jeśli zasięg nie jest ograniczony lub nieznany. Zaktualizuję to. Napisałem to zanim limit miał dla mnie znaczenie. Edytowanie tej odpowiedzi od dawna jest moim zdaniem. Niedługo znajdę czas.
nawfal

Czy funkcja Szudzika działa dla kombinacji lub permutacji. To wydaje się być permutacją, prawda? Jeśli chcę użyć kombinacji, czy mogę po prostu wyeliminować części algorytmu IF i Else?
Jamie Marshall,

Oto implementacja funkcji Szudzika w języku Python uogólniona na krotki dowolnej długości: gitlab.com/snippets/32559
Doctor J

47

Jeśli A i B można wyrazić za pomocą 2 bajtów, możesz je połączyć na 4 bajtach. Połóż A na najbardziej znaczącej połowie, a B na najmniej znaczącej połowie.

W języku C daje to (przy założeniu sizeof (short) = 2 i sizeof (int) = 4):

int combine(short A, short B)
{
    return A<<16 | B;
}

short getA(int C)
{
    return C>>16;
}

short getB(int C)
{
    return C & 0xFFFF;
}

3
combine()powinien return (unsigned short)(A<<16) | (unsigned short)(B); Aby liczby ujemne mogły być odpowiednio zapakowane.
Andy

2
@Andy A<<16wyjdzie poza granice. Powinno byćreturn (unsigned int)(A<<16) | (unsigned short)(B);
DanSkeel

15

Czy to w ogóle możliwe?
Łączycie dwie liczby całkowite. Oba mają zakres od -2 147 483 648 do 2 147 483 647, ale weźmiesz tylko pozytywy. To sprawia, że ​​2147483647 ^ 2 = 4,61169E + 18 kombinacji. Ponieważ każda kombinacja musi być unikalna ORAZ wynikać z liczby całkowitej, będziesz potrzebować jakiejś magicznej liczby całkowitej, która może zawierać taką liczbę liczb.

Czy moja logika jest wadliwa?


+1 Tak też myślę (chociaż wykonałem obliczenia, mówiąc, że kolejność A i B nie ma znaczenia)
lc.

4
Tak, twoja logika jest poprawna zgodnie z zasadą szufladki. Na szczęście pytający nie określił, czy liczba całkowita jest ograniczona, czy nie.
Nieznany

Tak, też to przemyślałem, ale pomyślałem, że przesłanie jest w gruncie rzeczy takie samo, więc nie zawracałem sobie głowy ponownym przeliczeniem.
Boris Callens

Właśnie zdałem sobie sprawę, że powinienem ponownie pobrać podręczniki do kalkulacji szans (dosłowne tłumaczenie z języka niderlandzkiego).
Boris Callens

2
@Boris: Kansrekening to „teoria prawdopodobieństwa”.
Stephan202

8

Standardowym matematycznym sposobem na dodatnie liczby całkowite jest użycie unikatowości faktoryzacji pierwotnej.

f( x, y ) -> 2^x * 3^y

Minusem jest to, że obraz ma tendencję do rozciągania się na całkiem szeroki zakres liczb całkowitych, więc jeśli chodzi o wyrażenie odwzorowania w algorytmie komputerowym, możesz mieć problemy z wyborem odpowiedniego typu dla wyniku.

Możesz to zmienić, aby radzić sobie z negatywnymi xiy kodując flagi o potęgach 5 i 7 terminów.

na przykład

f( x, y ) -> 2^|x| * 3^|y| * 5^(x<0) * 7^(y<0)

Matematyka jest w porządku. Ale, jak mówi Boris, jeśli chcesz uruchomić to jako program komputerowy, musisz wziąć pod uwagę skończoność maszyny. Algorytm będzie działał poprawnie dla podzbioru liczb całkowitych reprezentowanych w odpowiedniej maszynie.
Yuval F

2
Stwierdziłem to w drugim akapicie. Znaczniki w pytaniu wskazują „algorytm”, „matematyczne” i „deterministyczne”, a nie żaden konkretny język. Zakres wejściowy nie może być ograniczony, a środowisko może mieć nieograniczoną liczbę całkowitą typu „bigint”.
CB Bailey

8

Niech liczba abędzie pierwszą, bdrugą. Niech pbędzie a+1-tą liczbą pierwszą, qbyć b+1-tą liczbą pierwszą

Zatem wynikiem jest pq, jeśli a<b,lub 2pqjeśli a>b. Jeśli tak a=b, niech tak będzie p^2.


4
Wątpię, byś chciał rozwiązania NP.
user44242

1
Czy to nie daje tego samego wyniku dla a = 5, b = 14 i a = 6, b = 15?
Lieven Keersmaekers

3
Dwa produkty dwóch różnych liczb pierwszych nie mogą mieć tego samego wyniku (unikalny rozkład współczynnika pierwszego) a = 5, b = 14 -> wynik wynosi 13 * 47 = 611 a = 6, b = 15 -> wynik wynosi 17 * 53 = 901
ASk

4

Stworzenie mapowania nie jest trudne:

   1 2 3 4 5 użyj tego mapowania, jeśli (a, b)! = (B, a)
1 0 1 3 6 10
2 2 4 7 11 16
3 5 8 12 17 23
4 9 13 18 24 31
5 14 19 25 32 40

   1 2 3 4 5 użyj tego mapowania, jeśli (a, b) == (b, a) (mirror)
1 0 1 2 4 6
2 1 3 5 7 10
3 2 5 8 11 14
4 4 8 11 15 19
5 6 10 14 19 24


    0 1 -1 2 -2 użyj tego, jeśli potrzebujesz negatywnego / pozytywnego
 0 0 1 2 4 6
 1 1 3 5 7 10
-1 2 5 8 11 14
 2 4 8 11 15 19
-2 6 10 14 19 24

Ustalenie, w jaki sposób uzyskać wartość dla dowolnego a, b, jest nieco trudniejsze.


4

f(a, b) = s(a+b) + a, gdzie s(n) = n*(n+1)/2

  • To funkcja - jest deterministyczna.
  • Jest także iniekcyjny - f odwzorowuje różne wartości dla różnych par (a, b). Można to udowodnić wykorzystując fakt: s(a+b+1)-s(a+b) = a+b+1 < a.
  • Zwraca dość małe wartości - dobre, jeśli zamierzasz użyć go do indeksowania tablicy, ponieważ tablica nie musi być duża.
  • Jest przyjazny dla pamięci podręcznej - jeśli dwie pary (a, b) są blisko siebie, to f odwzorowuje na nich liczby, które są blisko siebie (w porównaniu z innymi metodami).

Nie rozumiem, co masz na myśli przez:

powinna zawsze dawać liczbę całkowitą po stronie dodatniej lub ujemnej liczb całkowitych

Jak pisać (większe niż), (mniej niż) znaki na tym forum?


2
Większe niż i mniejsze niż postacie powinny dobrze działać w środku backtick escapes.
TRiG,

Jest to równoważne funkcji parowania Cantora i jako takie nie działa z ujemnymi liczbami całkowitymi.
Davor Josipovic

4

Chociaż odpowiedź Stephan202 jest jedyną naprawdę ogólną, w przypadku liczb całkowitych z ograniczonego zakresu można lepiej. Na przykład, jeśli twój zakres wynosi 0..10 000, możesz:

#define RANGE_MIN 0
#define RANGE_MAX 10000

unsigned int merge(unsigned int x, unsigned int y)
{
    return (x * (RANGE_MAX - RANGE_MIN + 1)) + y;
}

void split(unsigned int v, unsigned int &x, unsigned int &y)
{
    x = RANGE_MIN + (v / (RANGE_MAX - RANGE_MIN + 1));
    y = RANGE_MIN + (v % (RANGE_MAX - RANGE_MIN + 1));
}

Wyniki mogą zmieścić się w jednej liczbie całkowitej dla zakresu do pierwiastka kwadratowego z liczności typu liczb całkowitych. Pakuje się to nieco wydajniej niż ogólniejsza metoda Stephan202. Dekodowanie jest również znacznie prostsze; nie wymagające pierwiastków kwadratowych, na początek :)


Czy jest to możliwe w przypadku pływaków?
Lukas


3

Sprawdź to: http://en.wikipedia.org/wiki/Pigeonhole_principle . Jeśli A, B i C są tego samego typu, nie można tego zrobić. Jeśli A i B to 16-bitowe liczby całkowite, a C to 32-bit, możesz po prostu użyć przesunięcia.

Sama natura algorytmów mieszających polega na tym, że nie mogą one zapewnić unikatowego skrótu dla każdego innego wejścia.


2

Oto rozszerzenie kodu @DoctorJ na nieograniczone liczby całkowite oparte na metodzie podanej przez @nawfal. Może kodować i dekodować. Działa z normalnymi tablicami i tablicami liczbowymi.

#!/usr/bin/env python
from numbers import Integral    

def tuple_to_int(tup):
    """:Return: the unique non-negative integer encoding of a tuple of non-negative integers."""
    if len(tup) == 0:  # normally do if not tup, but doesn't work with np
        raise ValueError('Cannot encode empty tuple')
    if len(tup) == 1:
        x = tup[0]
        if not isinstance(x, Integral):
            raise ValueError('Can only encode integers')
        return x
    elif len(tup) == 2:
        # print("len=2")
        x, y = tuple_to_int(tup[0:1]), tuple_to_int(tup[1:2])  # Just to validate x and y

        X = 2 * x if x >= 0 else -2 * x - 1  # map x to positive integers
        Y = 2 * y if y >= 0 else -2 * y - 1  # map y to positive integers
        Z = (X * X + X + Y) if X >= Y else (X + Y * Y)  # encode

        # Map evens onto positives
        if (x >= 0 and y >= 0):
            return Z // 2
        elif (x < 0 and y >= 0 and X >= Y):
            return Z // 2
        elif (x < 0 and y < 0 and X < Y):
            return Z // 2
        # Map odds onto negative
        else:
            return (-Z - 1) // 2
    else:
        return tuple_to_int((tuple_to_int(tup[:2]),) + tuple(tup[2:]))  # ***speed up tuple(tup[2:])?***


def int_to_tuple(num, size=2):
    """:Return: the unique tuple of length `size` that encodes to `num`."""
    if not isinstance(num, Integral):
        raise ValueError('Can only encode integers (got {})'.format(num))
    if not isinstance(size, Integral) or size < 1:
        raise ValueError('Tuple is the wrong size ({})'.format(size))
    if size == 1:
        return (num,)
    elif size == 2:

        # Mapping onto positive integers
        Z = -2 * num - 1 if num < 0 else 2 * num

        # Reversing Pairing
        s = isqrt(Z)
        if Z - s * s < s:
            X, Y = Z - s * s, s
        else:
            X, Y = s, Z - s * s - s

        # Undoing mappint to positive integers
        x = (X + 1) // -2 if X % 2 else X // 2  # True if X not divisible by 2
        y = (Y + 1) // -2 if Y % 2 else Y // 2  # True if Y not divisible by 2

        return x, y

    else:
        x, y = int_to_tuple(num, 2)
        return int_to_tuple(x, size - 1) + (y,)


def isqrt(n):
    """":Return: the largest integer x for which x * x does not exceed n."""
    # Newton's method, via http://stackoverflow.com/a/15391420
    x = n
    y = (x + 1) // 2
    while y < x:
        x = y
        y = (x + n // x) // 2
    return x

2

Co powiesz na coś o wiele prostszego: Biorąc pod uwagę dwie liczby, A i B niech będą stratatation: 'A' + ';' + „B”. Niech wyjście będzie hash (str). Wiem, że nie jest to matematyczna odpowiedź, ale prosty skrypt python (który ma wbudowaną funkcję skrótu) powinien wykonać to zadanie.


2
ale (8,11) i (81,1) są odwzorowane na ten sam numer 811
Leevi L

To dobra uwaga. Możesz rozwiązać ten problem, po prostu dodając symbol na środku. Tak więc dla (8, 11) hash ciąg „8-11”, a dla (81, 1) hash ciąg „81-1”. Ogólnie rzecz biorąc dla skrótu (A, B) ciąg „AB”. (Wiem, że to brzmi dziwnie, ale powinno działać).
Madhav Nakar,

jest również błędne, ponieważ zadaniem tego jest odwzorowanie dwóch liczb całkowitych na nową liczbę całkowitą, a nie ciąg znaków z symbolem
Leevi L

Pochodzę raczej z perspektywy CS niż matematycznej (dla rozwiązań matematycznych spójrz na powyższe odpowiedzi). Biorę dwie liczby całkowite, przekształcając je w ciąg, a następnie zamieniam w liczbę całkowitą. Zasadniczo tak odwzorowuję dwie liczby całkowite na nowe.
Madhav Nakar

1

To, co sugerujesz, jest niemożliwe. Zawsze będziesz mieć kolizje.

Aby zmapować dwa obiekty na inny pojedynczy zestaw, zmapowany zestaw musi mieć minimalną wielkość oczekiwanej liczby kombinacji:

Zakładając 32-bitową liczbę całkowitą, masz 2147483647 liczb całkowitych dodatnich. Wybranie dwóch z nich, w przypadku których kolejność nie ma znaczenia i przy powtarzaniu daje 2305843008139952128 kombinacji. Nie pasuje to dobrze do zestawu 32-bitowych liczb całkowitych.

Możesz jednak zmieścić to mapowanie w 61 bitach. Korzystanie z 64-bitowej liczby całkowitej jest prawdopodobnie najłatwiejsze. Ustaw wysokie słowo na mniejszą liczbę całkowitą, a niskie słowo na większą.


1

Załóżmy, że masz 32-bitową liczbę całkowitą. Dlaczego nie przenieść A do pierwszej 16-bitowej połowy, a B do drugiej?

def vec_pack(vec):
    return vec[0] + vec[1] * 65536;


def vec_unpack(number):
    return [number % 65536, number // 65536];

Poza tym, że jest tak wydajny, jak to tylko możliwe i tani w obliczeniach, naprawdę fajnym efektem ubocznym jest to, że możesz wykonać matematykę wektorową na zapakowanej liczbie.

a = vec_pack([2,4])
b = vec_pack([1,2])

print(vec_unpack(a+b)) # [3, 6] Vector addition
print(vec_unpack(a-b)) # [1, 2] Vector subtraction
print(vec_unpack(a*2)) # [4, 8] Scalar multiplication

0

niech mamy dwie liczby B i C, kodując je w jedną liczbę A.

A = B + C * N

gdzie

B = A% N = B

C = A / N = C


2
Jak wybrać N, aby ta reprezentacja była unikalna? Jeśli rozwiążesz ten problem, czym różni się ta odpowiedź od powyższych?
Prune

Należy dodać, że N musi być większy niż B i C.
Radoslav Stoyanov

0

Biorąc pod uwagę dodatnie liczby całkowite A i B, niech D = liczba cyfr A ma, a E = liczba cyfr B ma Wynik może być połączeniem D, 0, E, 0, A i B.

Przykład: A = 300, B = 12. D = 3, E = 2 wynik = 302030012. Wykorzystuje to fakt, że jedyną liczbą rozpoczynającą się od 0 jest 0,

Pro: Łatwe do kodowania, łatwe do odkodowania, czytelne dla człowieka, cyfry znaczące można najpierw porównać, możliwość porównania bez obliczeń, proste sprawdzanie błędów.

Minusy: Rozmiar wyników jest problemem. Ale to w porządku, dlaczego i tak przechowujemy w komputerze nieograniczone liczby całkowite.


0

Jeśli chcesz mieć większą kontrolę, na przykład alokuj bity X dla pierwszej liczby i bity Y dla drugiej liczby, możesz użyć tego kodu:

class NumsCombiner
{

    int num_a_bits_size;
    int num_b_bits_size;

    int BitsExtract(int number, int k, int p)
    {
        return (((1 << k) - 1) & (number >> (p - 1)));
    }

public:
    NumsCombiner(int num_a_bits_size, int num_b_bits_size)
    {
        this->num_a_bits_size = num_a_bits_size;
        this->num_b_bits_size = num_b_bits_size;
    }

    int StoreAB(int num_a, int num_b)
    {
        return (num_b << num_a_bits_size) | num_a;
    }

    int GetNumA(int bnum)
    {
        return BitsExtract(bnum, num_a_bits_size, 1);
    }

    int GetNumB(int bnum)
    {
        return BitsExtract(bnum, num_b_bits_size, num_a_bits_size + 1);
    }
};

Używam w sumie 32 bitów. Chodzi o to, że jeśli chcesz na przykład, aby pierwsza liczba wynosiła do 10 bitów, a druga liczba do 12 bitów, możesz to zrobić:

NumsCombiner nums_mapper(10/*bits for first number*/, 12/*bits for second number*/);

Teraz możesz przechowywać w num_amaksymalnej liczbie, która jest 2^10 - 1 = 1023w num_bnaximum wartości 2^12 - 1 = 4095.

Aby ustawić wartość dla liczb A i B:

int bnum = nums_mapper.StoreAB(10/*value for a*/, 12 /*value from b*/);

Teraz bnumsą wszystkie bity (łącznie 32 bity. Możesz zmodyfikować kod, aby używał 64 bitów) Aby uzyskać num a:

int a = nums_mapper.GetNumA(bnum);

Aby uzyskać num b:

int b = nums_mapper.GetNumB(bnum);

EDYCJA: bnummoże być przechowywana wewnątrz klasy. Nie zrobiłem tego, ponieważ własne potrzeby podzieliłem kod i mam nadzieję, że będzie on pomocny.

Dzięki za źródło: https://www.geeksforgeeks.org/extract-k-bits-given-position-number/ za funkcję wyodrębniania bitów i dziękuję również za mouvicielodpowiedź w tym poście. Używając ich do źródeł, mogłem znaleźć bardziej zaawansowane rozwiązanie

Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.