3

任意の長さの2進数を正確な3進数表現に変換する必要があります。理想的には、ビットの配列が与えられるchar buffer[n]と、アルゴリズムはトリットの配列（ビットのアナログ）を生成でき、その逆も可能です。そのようなアルゴリズムはありますか？

int個人を3進数に変換する方法を知っています。

int nth_trit(int num, int n)
{
    for(int i = 0; i < n; i++)
        num /= 3;

    return num % 3;
}

残念ながら、ビットストリームでlong long long intは十分ではありません。よくわかりませんが、大きな整数ライブラリを使用すれば十分だと思います。また、3進表現を計算するためのより良い方法があるはずだと感じています。

視覚的な例：

// Conversion is simple(short stream)
Binary  - 0 1 0 0 1 0 0 1
Decimal -             7 3
Ternary -         2 2 0 1

// Conversion is hard(long stream)
Binary  - 1 0 1 0 0 0 0 1 ..........
Ternary - ? ? ?

intショートストリームは、にうまく収まるのでnth_trit関数を使用できますが、ロングストリームは使用できないため、単純です。大きな整数ライブラリを使用する以外に、簡単な解決策はありません。

4

4 に答える 4

2

すべての 3 進数がすべて 2 進数の 1 に依存していることを示すことができます。したがって、ビットの文字列全体を読み取ってから変換を行うよりも優れた方法はありません。

于 2012-08-18T09:34:22.117 に答える
1

ビットバッファが長い場合、アルゴリズムはあまり良くありません。これは、各出力トリットが のより小さい値にも必要なすべての除算を繰り返すためですn。したがって、このアルゴリズムを「bignum」算術に変換することは、あなたが望むものではありません。

別のアプローチ: ビットを左から右にスキャンし、新しいビットごとに以前の値を更新します。

val = val * 2 + bit

nトリットを含む 3進数t[i]の値は

sum(i = 0 .. n-1) t[i] * 3^i

したがって、val新しくスキャンされたビットの更新済みの 3 進数表現は、次のようになります。

[ 2 * sum(i = 0 .. n-1) t[i] * 3^i ] + bit
    = bit + sum(i = 0 .. n-1) 2 * t[i] * 3^i 
    = 2 * t[0] + b + sum(i = 1 .. n) 2 * t[i] * 3^i

コードを単純にするために、符号なし文字の配列でトリットを計算してみましょう。完成後、好きな方法で再梱包できます。 

#include <stdio.h>

// Compute the trit representation of the bits in the given
// byte buffer.  The highest order byte is bytes[0].  The
// lowest order trit in the output is trits[0].  This is 
// not a very efficient algorithm, but it doesn't use any
// division.  If the output buffer is too small, high order
// trits are lost.
void to_trits(unsigned char *bytes, int n_bytes, 
              unsigned char *trits, int n_trits)
{
  int i_trit, i_byte, mask;

  for (i_trit = 0; i_trit < n_trits; i_trit++)
    trits[i_trit] = 0;

  // Scan bits left to right.
  for (i_byte = 0; i_byte < n_bytes; i_byte++) {

    unsigned char byte = bytes[i_byte];

    for (mask = 0x80; mask; mask >>= 1) {
      // Compute the next bit.
      int bit = (byte & mask) != 0;

      // Update the trit representation
      trits[0] = trits[0] * 2 + bit;
      for (i_trit = 1; i_trit < n_trits; i_trit++) {
        trits[i_trit] *= 2;
        if (trits[i_trit - 1] > 2) {
          trits[i_trit - 1] -= 3;
          trits[i_trit]++;
        }
      }
    }
  }
}

// This test uses 64-bit quantities, but the trit 
// converter will work for buffers of any size.
int main(void)
{
  int i;

  // Make a byte buffer for an easy to recognize value.
  #define N_BYTES 7
  unsigned char bytes [N_BYTES] = 
    { 0xab, 0xcd, 0xef, 0xff, 0xfe, 0xdc, 0xba };

  // Make a trit buffer.  A 64 bit quantity may need up to 42 trits.
  #define N_TRITS 42
  unsigned char trits [N_TRITS];

  to_trits(bytes, N_BYTES, trits, N_TRITS);

  unsigned long long val = 0;
  for (i = N_TRITS - 1; i >= 0; i--) {
    printf("%d", trits[i]);
    val = val * 3 + trits[i];
  }
  // Should prinet value in original byte buffer.
  printf("\n%llx\n", val);

  return 0;
}
于 2012-08-18T05:36:09.193 に答える
1

2 による乗算/除算はどの基数でも簡単なので、基数を 2 進数に変換する最も簡単な方法は、2 で乗算/除算を繰り返し、キャリー/パリティを追跡することです。

#include <algorithm>
#include <cstdint>
#include <functional>
#include <iostream>
#include <iterator>
#include <vector>

// in: a vector representing a bitstring, with most-significant bit first.
// out: a vector representing a tritstring, with least-significant trit first.
static std::vector<uint8_t> b2t(const std::vector<bool>& in) {
  std::vector<uint8_t> out;
  out.reserve(in.size());  // larger than necessary; will trim later
  // for each digit (starting from the most significant bit)
  for (bool carry : in) {
    // add it to the tritstring (starting from the least significant trit)
    for (uint8_t& trit : out) {
      // double the tritstring, carrying overflow to higher places
      uint8_t new_trit = 2 * trit + carry;
      carry = new_trit / 3;
      trit = new_trit % 3;
    }
    if (carry) {
      // overflow past the end of the tritstring; add a most-significant trit
      out.push_back(1);
    }
  }
  out.reserve(out.size());
  return out;
}

// in: a vector representing a tritstring, with most-significant trit first.
// out: a vector representing a bitstring, with least-significant bit first.
static std::vector<bool> t2b(std::vector<uint8_t> in) {
  std::vector<bool> out;
  out.reserve(2 * in.size());  // larger than necessary; will trim later
  bool nonzero;
  do {
    nonzero = false;
    bool parity = false;
    for (uint8_t& trit : in) {
      // halve the tritstring, starting from the most significant trit
      uint8_t new_trit = trit + 3 * parity;
      parity = new_trit & 1;
      nonzero |= trit = new_trit / 2;
    }
    // the division ended even/odd; add a most-signiticant bit
    out.push_back(parity);
  } while (nonzero);
  out.reserve(out.size());
  return out;
}

int main() {
  bool odd = false;
  std::string s;
  while (std::cin >> s) {
    if ((odd = !odd)) {
      std::vector<bool> in(s.size());
      std::transform(s.begin(), s.end(), in.begin(),
          [](char c) {return c - '0';});
      std::vector<uint8_t> out(b2t(in));
      std::copy(out.rbegin(), out.rend(),
          std::ostream_iterator<int>(std::cout));
      std::cout << std::endl;
    } else {
      std::vector<uint8_t> in(s.size());
      std::transform(s.begin(), s.end(), in.begin(),
          [](char c) {return c - '0';});
      std::vector<bool> out(t2b(in));
      std::copy(out.rbegin(), out.rend(),
          std::ostream_iterator<int>(std::cout));
      std::cout << std::endl;
    }
  }
  return 0;
}

$ ./a.out 
1011
102
102
1011
10001100001101010011010010111000011011101000111101011101000110100101101101111110110011010010111100010110100010101011010100101100001101001000000111011110101001000100011010111011000111101110111001111110110011101011101101001001110010111111100011000110011000111110110111011110110110001111011011011000100101010010111010000110101011010100011010110110000010110111000111000110101000000110000001111110101110010000011000110001010000001001100011000000100100100001100101111000101001001010101101101000011100110001111011110001
12010110110220200020211012001000211110222212120220002002120120111221021120100122221020011120010202110111112112110201211201120222000011010100122122121211112101111121002110102112000111200002121211002022100220211220220111010210200222021221020122012102101010100001122200011110210221120122022011202201002002001221211001221112001
12010110110220200020211012001000211110222212120220002002120120111221021120100122221020011120010202110111112112110201211201120222000011010100122122121211112101111121002110102112000111200002121211002022100220211220220111010210200222021221020122012102101010100001122200011110210221120122022011202201002002001221211001221112001
10001100001101010011010010111000011011101000111101011101000110100101101101111110110011010010111100010110100010101011010100101100001101001000000111011110101001000100011010111011000111101110111001111110110011101011101101001001110010111111100011000110011000111110110111011110110110001111011011011000100101010010111010000110101011010100011010110110000010110111000111000110101000000110000001111110101110010000011000110001010000001001100011000000100100100001100101111000101001001010101101101000011100110001111011110001
^D

(1011 2 = 8+2+1 = 11 = 9 + 2 = 102 3 )
(10001100001101010011010010111000011011101000111101011101000110100101101101111110110011010010111100010110100010101011010100101100001101001000000111011110101001000100011010111011000111101110111001111110110011101011101101001001110010111111100011000110011000111110110111011110110110001111011011011000100101010010111010000110101011010100011010110110000010110111000111000110101000000110000001111110101110010000011000110001010000001001100011000000100100100001100101111000101001001010101101101000011100110001111011110001 2= 7343280200542654154029818354420920722408633707396360612751407162736942742985658428558632312175242897575484682660836397639769592568209070221085927986634481 = 12010110110220200020211012001000211110222212120220002002120120111221021120100122221020011120010202110111112112110201211201120222000011010100122122121211112101111121002110102112000111200002121211002022100220211220220111010210200222021221020122012102101010100001122200011110210221120122022011202201002002001221211001221112001 9 )

于 2012-08-18T08:55:49.810 に答える
-1

バランスのとれた Ternary/Trinary の方が優れています。{-1, 0, 1} このような方法で出力を行います。

于 2013-02-03T20:34:04.927 に答える