Быстровычислимая функция для целого

kataich

Может, кому придёт в голову такая функция 'int f(int x)', что:
a) Все байты в значении f(x) ненулевые
б) Функция и обратная к ней 'легко' вычислялись
Не могу чётко формализовать, что значит легко. К примеру, несколько битовых операций.
(это нормально, если f(x) будет работать для всех int, кромер, INT_MAX или INT_MIN)
Спасибо
Update Прошу прощения, я пытался формализовать то, что у меня есть и совершил ошибку.
Пожалуйста, рассмотрите корректную формализацию ниже


int f_direct(int x, char *key)

int f_invert(int x, char key)

Update предложил красивую идею
Идея такая: в key храним байт, который не совпадает ни с одним байтом из четырёх байтов, образающих x. И делаем побайтный XOR с ним. Такой байт можно найти из классического трюка матанализа про несчетность множества вещественных чисел – строим байт, который хотя бы в одном бите не совпадает с байтами числа x.

Maurog

f(x) = 0xFFFFFFFF;

kataich

f(x) = 0xFFFFFFFF;
а обратная? :)

Maurog

а обратная?
едрить, а слона-то я и не приметил! :grin:

istran

1. Ты хочешь взаимно-однозначную функцию (т.к. предполагается существование обратной).
2. При этом ты исключаешь из области значений все числа, имеющие нулевой байт.
Чтобы выполнялось 1, надо, чтобы множества аргументов и значений имели одинаковый размер. Это противоречит условию 2. Или я неправилно понял?

Maurog

Не могу чётко формализовать, что значит легко. К примеру, несколько битовых операций.
(это нормально, если f(x) будет работать для всех int, кромер, INT_MAX или INT_MIN)
надо исключить еще немного чисел из области определения, т.к кол-во возможных значений меньше, чем кол-во входных значений. какие-то входы могут слипнуться, то бишь обратная функции не будет существовать

capxaH

Может я сейчас глупость скажу, но получается что ты хочешь отобразить взаимно однозначно множество интов, на множество которое примерно равно 6/10 этого множества, а позволяешь выкинуть только 2 числа.

kataich

Прошу прощения, я пытался формализовать то, что у меня есть и совершил ошибку.
Пожалуйста, рассмотрите корректную формализацию ниже


int f_direct(int x, char *key)

int f_invert(int x, char key)

Другими словами, функция f берет на вход int и на выходе получается int, у которого все байты ненулевые, также может сохранить некий 'ключ', который потом передаётся обратной функции.
Обратная функция берет ключ и зашифрованный объект и получает оригинальное число.
С такими условиями f существует, к примеру, все старшие биты числа int делаем равными 1, а оригинальные значения сохраняем в key.
Но, возможно, кто-то знает 'красивое' решение в одну строчку?

istran

Прямая *key = x; return -1;
Обратная return key;
=)
Какая изначальная задача?

kataich

sizeof(key) < sizeof(int)

Maurog

int f_direct(int x, char *key)
int f_invert(int x, char key)
а ручки-то вот они :


int f_direct(int x, int& key)

{

  key = x;

  return 0;

}



int f_invert(int, int key)

{

  return key;

}

:grin:

Maurog

Какая изначальная задача?
+1
опередил! :o

kataich

Какая изначальная задача?
Пожалуйста, есть буфер размером 5 байт. На вход подаётся целое число int.
Необходимо сохранить целое число в буфере таким образом, что все байты буфера ненулевые.

istran

ОК, не заметил. Ну твой вариант с битами неплох, может даже существует какая-нибудь хитрая x86 инструкция, которая это делает.

kataich

Я не совсем понял это решение:


int f_invert(int, int key)

{

  return key;

}

требовалось же


int f_invert(int x, char key)

marat7256

Не уверен, что стало понятнее ЗАЧЕМ ЭТО ВСЕ :grin:

kataich

С удовольствием объясню это всё, если это необходимо :)

marat7256

Ну, и?

kataich

Зачем мне хочется сделать все байты ненулевыми?
Кстати, можно догадаться из общих соображений :)
Хочу в этом буфере хранить некоторую информацию, но библиотека, которой я передаю этот буфер
где-то внутри себя используюет str* функции для копирования.

Marinavo_0507

ну очевидно что нужно закодировать число для передачи по каналу, где нулевой байт имеет специальное значение и не может использоваться

banderon

Код на коленке написан, даже не проверял, что он компилируется :grin:


int f_direct(int x, char *key) {

    *key = ~x && 0x11000000)>>24 || (x && 0x002200000)>>16 || (x && 0x00004400)>>8 || (x && 0x00000088;

    return x ^ (*key || *key<<8 || *key<<16 || *key<<24);

}

int f_invert(int x, char key) {

    return x ^ (key || key<<8 || key<<16 || key<<24);

}

Идея такая: в key храним байт, который не совпадает ни с одним байтом из четырёх байтов, образающих x. И делаем побайтный XOR с ним. Такой байт можно найти из классического трюка матанализа про несчетность множества вещественных чисел – строим байт, который хотя бы в одном бите не совпадает с байтами числа x.
В моём коде такой байт не совпадает ровно в двух битах с каждым из четырых байтов. Легко расширяется на случай long int

banderon

Не знаю, насколько современные компиляторы хорошо оптимизируют код. Может быть такая замена будет быстрее работать.


unsigned int m = x && 0x11224488;

m |= m >> 16;

m |= m >> 8;

*key = m && 0xff;

m |= m << 8;

m |= m << 16;

return x ^ ~m;

kataich

Идея, на мой взгляд, чудесна! Огромное спасибо.

yolki

XYZ ?

kataich

Я не понял, что это?

yolki

http://www.gunsmoker.ru/2008/10/x-y-z.html

yolki

то ли тебе нужен hashtable, то ли экранирование для странного канала

vall

unsigned int m = x && 0x11224488;

m |= m >> 16;

m |= m >> 8;

*key = m && 0xff;

m |= m << 8;

m |= m << 16;

return x ^ ~m;

вроде так


*key = x & 0x11224488) * 0x01010101) >> 24;

return x ^ ~(*key * 0x01010101);

Andbar

Хочу в этом буфере хранить некоторую информацию, но библиотека, которой я передаю этот буфер
где-то внутри себя используюет str* функции для копирования.
в base64 закодировать не вариант?

kataich

Конечно, можно, но варианты и - гораздо изящнее, не правда ли?

vall

на самом деле наверняка можно построить кодирование которое ещё лучше ложится на 32-битную арифметику. в таких делах лучше подгонять не код к идее а идею к коду.

Maurog

вроде так
*key = x & 0x11224488) * 0x01010101) >> 24;
при x = 0 получаем key = 0, что вроде пытались избежать

kataich

Это легко обойти, если брать не по два бита из каждого байта, а лишь по одному,
то есть вместо 0x11224488 брать 0x01020408, тогда останутся еще биты, чтобы
и key сделать ненулевым.
Оставить комментарий
Имя или ник:
Комментарий: