Developing.ru

Сионист писал(а):Нет конечно. Восемь жалких байт - это уже большое число?

Ах, оно из восьми байт состоит? Так бы и сказал сразу. Я просто вот это прочёл сначала:

Сионист писал(а):sizeof(x) строго меньше 256.

Извини, я каждый раз забываю, что ты неглубоко С++ знаешь. Если что, sizeof возвращает размер типа в минимальных адресуемых единицах (на большинстве систем минимальная адресуемая единица - это char). То есть, если выразится понятнее, sizeof возвращает размер типа не в битах, а в байтах.

Я к тому, что правильно было написать:

sizeof(x) строго меньше 8

Тогда бы я не задал вопроса о том, как хранится число.

И кстати, если у тебя это обычное число long long int, то вот это сообщение вообще забавным получается.

Сионист писал(а):В каком месте сказано, что число на байты уже разобрано?

То, что ты не использовал тот факт, что на байты число как раз уже разобрано хотя бы потому, что просто хранится в памяти побайтно, в этом уже твоя проблема.

Сионист писал(а): Я даже не использую тот факт, что байты одной переменной хранятся подряд. Они так хранятся, но это не используется.

И в том, что не используешь порядок, тоже твоя проблема. В анализе машинного представления числа как раз вся соль задачки.

Для проверки того, что машинное представление работает, добавь в мой код в main ещё две строки и увидишь второе "Yes" после запуска:

Код: Выделить всё

   unsigned long long int nLongNumber = 0x0706050403020100;
   std::cout << (ContainsConsecutiveValues((unsigned char*)&nLongNumber, sizeof(nLongNumber)) ? "Yes" : "No") << std::endl;

В общем, вот окончательно решение задачи:

Код: Выделить всё

#include <iostream>

// Checks whether array contains consecutive values from 0 to nSize-1 in arbitrary order.
bool ContainsConsecutiveValues(unsigned char arrNumbers[], unsigned int nSize)
{
   bool arrExists[nSize];
   for (int i = 0; i < nSize; arrExists[i++] = false);

   for (unsigned int i = 0; i < nSize; ++i)
   {
      // Value is not in range [0..nSize-1]
      if (arrNumbers[i] >= nSize) return false;

      if (arrExists[arrNumbers[i]])
      {
         // Repetition of the value
         return false;
      }
      else
      {
         // Marking the value as met
         arrExists[arrNumbers[i]] = true;
      }
   }

   // If we are here, then all the checks are OK, so return true
   return true;
}

// Overloaded version for 64-bit number
bool ContainsConsecutiveValues(unsigned long long nLongNumber)
{
   return ContainsConsecutiveValues((unsigned char*)&nLongNumber, sizeof(nLongNumber));
}

int main()
{
   unsigned char arrNumbers[] = { 1, 0, 3, 2 };
   std::cout << (ContainsConsecutiveValues(arrNumbers, sizeof(arrNumbers)) ? "Yes" : "No") << std::endl;
   unsigned long long int nLongNumber = 0x0706050403020100;
   std::cout << (ContainsConsecutiveValues(nLongNumber) ? "Yes" : "No") << std::endl;
   return 0;
}

Результат запуска:

Yes
Yes

Romeo писал(а):Я поэтому и спросил, первым делом, как они хранятся. А ты так и не ответил на тот вопрос. И даже сейчас ответа не дал.

Потому что это не имеет значения. Достаточно того, что это число. Целое беззнаковое.

Romeo писал(а):Ах, оно из восьми байт состоит?

Может и из четёрёх. Так бы и сказал сразу.

Romeo писал(а):Я просто вот это прочёл сначала:

1. Без ограничения сверху возможны ответы типа: "В будущем задача может стать не решаемой, так как разрядность байта может оказаться недостаточной для представления числа, на единицу меньшего количества байт в числе".
2. Длинную арифметику тоже кто нибудь может помянуть. В том же контексте. При этом решение ни как не должно зависеть от конкретного способа хранения, должно быть достаточно, если для числа реализованы необходимые операции.

Romeo писал(а): Извини, я каждый раз забываю, что ты неглубоко С++ знаешь.

Достаточно, чтоб знать операции с беззнаковым целым.

Romeo писал(а):Если что, sizeof возвращает размер типа в минимальных адресуемых единицах (на большинстве систем минимальная адресуемая единица - это char). То есть, если выразится понятнее, sizeof возвращает размер типа не в битах, а в байтах.

1. А где у меня хоть слово о битах?
2. Какая разница, как байт называется в языке программирования? Это всё равно байт на всех платформах кроме сетуни.

Romeo писал(а):И в том, что не используешь порядок, тоже твоя проблема. В анализе машинного представления числа как раз вся соль задачки.

Нет. Всё гораздо проще:

Код: Выделить всё

 size_t Counts[sizeof(Order)];
 uint8_t Digit;
 size_t   *Count;
 for (Count=Counts+sizeof(x)-1; Count>=Counts; --Count)
 {
  (*Count)=0;
 }
 do
 {
  Digit=x%0x100;
  if (Digit<sizeof(x))
  {
   Count=Counts+Digit;
   ++(*Count);
   if ((*Count)!=1)
   {
    return false;
   }
  }
  else
  {
   return false;
  }
  x/=0x100;
 } while (x!=0);
 for (Count=Counts+sizeof(x)-1; Count>=Counts; --Count)
 {
  if ((*Count)!=1)
  {
   return false;
  }
 }
 return true;

, но это только для одного размера байта.
1. Можно оптимизировать, сохранив поддержку всех реализованных типов беззнаковых двоичных целых фиксированных разрядностей вне зависимости от степени их стандартности/отсебячности, конкретного их внутреннего представления и private/protected/public для членов, отвечающих за хранение?
2. Можно добавить поддержку байтов другого размера? Так чтоб не менять делитель вручную для каждого размера байта.

Сионист писал(а): 1. Без ограничения сверху возможны ответы типа: "В будущем задача может стать не решаемой, так как разрядность байта может оказаться недостаточной для представления числа, на единицу меньшего количества байт в числе".

Ты сам-то понимаешь, что пишешь? Если разрядность байта будет недостаточна для представления числа, то задача вообще становится некорректной, так как в условии сказано, что мы должны разобрать число побайтно. Не может храниться в байте число больше, чем 255 по определению. Либо условие нужно будет менять на то, что разбирать число пословно, либо паять свой компьютер, в котором в байте больше восьми бит. И даже если условие будет изменено, то в моей программе только поменяется тип элементов входного массива с unsigned char на unsigned short, а тебе же твою программу переписать с нуля придётся... И ты после этого о переносимости своего кода заикаешься?

Сионист, вот скажи, зачем ты создаёшь подобные темы, в которых спрашиваешь совета, как лучше делать, затем критикуешь предлагаемые решения, на которые люди тратят своё время и свои силы, а потом всё равно всё делаешь кривовато и дилетантски, но зато по-своему? Я сколько раз уже зарекался залезать в твои темы и вообще как-то тебе помогать, так как это бесполезная трата времени и нервов, но у меня не получается себя сдерживать. То, что я напишу дальше, не читай, и не отвечай на это сообщение, так как оно адресовано не тебе, а тем людям, которые возможно найдут эту тему в поисковике и захотят узнать, как написать эту задачу максимально оптимально.

И так, господа, если число является встроенным типом, у нас есть гарантия, что оно располагается в памяти непрерывно. Это справедливо абсолютно для всех архитектур и операционных систем. Разница может быть только в порядке байт (см. подробнее little-endian, big-engiad, middle-endian в гугле). Но, так как по условиям задачи порядок может быть произвольным, нас эта часть как раз не волнует. Гарантия непрерывности есть и со стороны стандарта С++, так что если кто-нибудь спаяет свой компьютер, который будет работать совсем не так, как это принято было ранее, то ему придётся написать для него и свой компилятор со своим собственным стандартом.

Опираясь на всё вышесказанное, предоставляю максимально оптимальное решение для всех целочисленных типов.

Код: Выделить всё

#include <iostream>

// Checks whether array contains consecutive values from 0 to nSize-1 in arbitrary order.
bool ContainsConsecutiveValues(const unsigned char arrNumbers[], unsigned int nSize)
{
   bool arrExists[nSize]] = false);

   for (unsigned int i = 0; i < nSize; ++i)
   {
      // Value is not in range [0..nSize-1]
      if (arrNumbers[i] >= nSize) return false;

      if (arrExists[arrNumbers[i]])
      {
         // Repetition of the value
         return false;
      }
      else
      {
         // Marking the value as met
         arrExists[arrNumbers[i]] = true;
      }
   }

   // If we are here, then all the checks are OK, so return true
   return true;
}

// Overloaded version for 1-byte number (optimized)
bool ContainsConsecutiveValues(unsigned char n)
{
   return (0 == 0x00);
}

// Overloaded version for 2-byte number (optimized)
bool ContainsConsecutiveValues(unsigned short n)
{
   return (0x0001 == n) || (0x0100 == n);
}

// Overloaded version for 4-byte number
bool ContainsConsecutiveValues(unsigned long n)
{
   return ContainsConsecutiveValues((const unsigned char*)&n, sizeof(n));
}

// Overloaded version for 8-byte number
bool ContainsConsecutiveValues(unsigned long long n)
{
   return ContainsConsecutiveValues((const unsigned char*)&n, sizeof(n));
}

int main()
{
   {
      const unsigned char n = 0x00;
      std::cout << (ContainsConsecutiveValues(n) ? "Yes" : "No") << std::endl;
   }

   {
      const unsigned short n = 0x0100;
      std::cout << (ContainsConsecutiveValues(n) ? "Yes" : "No") << std::endl;
   }

   {
      const unsigned long n = 0x03020100;
      std::cout << (ContainsConsecutiveValues(n) ? "Yes" : "No") << std::endl;
   }

   {
      const unsigned long long int n = 0x0706050403020100;
      std::cout << (ContainsConsecutiveValues(n) ? "Yes" : "No") << std::endl;
   }

   {
      // 16-byte number has no buid-in type, so it is represented as array of bytes
      const unsigned char arrNumbers[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 };
      std::cout << (ContainsConsecutiveValues(arrNumbers, sizeof(arrNumbers)) ? "Yes" : "No") << std::endl;
   }

   return 0;
}

Получать сам массив сырых байтов не надо. Надо только проверить условие на значение его элементов, которые они приняли бы, если такой массив всё таки из числа получить.

Ты сам-то понимаешь, что пишешь? Если разрядность байта будет недостаточна для представления числа, то задача вообще становится некорректной, так как в условии сказано, что мы должны разобрать число побайтно.

Дано число типа uint16_t, равное 273. Докажи, что его нельзя разобрать на два байта. Речь о другом.
1. Нельзя гарантировать, что в будущем не будет реализован в каком нибудь компиляторе тип беззнаковых целых, разрядность которого будет больше 256-ти.
2. Длинная двоичная арифметика фиксированной разрядности также может иметь разрядность хоть 1024 байта.
Поэтому если я не напишу ограничение на разрядность сверху, то тут же получаем вывод о том, что задача в общем случае не решаема, так как если разрядность больше 256-ти, то байтов в числе тоже больше 256-ти, то есть как минимум 257. Разобрать то его на байты можно всё равно, но если байтов 257, или больше, то они:
1. Вообще не могут принимать все значения от 0 до sizeof(x)-1, так как sizeif(x)-1 не лезет в байт.
2. Не могут принимать все значения ровно по разу, так как байтов больше, чем возможных вариантов их значений.
А так получаем, что не зависимо от того, как будет меняться стандарт, развиваться процессоры и кому взбредёт в голову встроить в диалект длинно-арифметическую отсебятину, в версиях обсуждаемой функции такой тип поддерживать не надо.
1. sizeof(x)<256.
2. Тип реализован. Как именно, является ли он стандартным или отсебячьим, встроен ли в диалект, или это отсебятина уже прикладника, значения не имеет. Он реализован и поддерживает все стандартные операции над беззнаковыми целыми.
3. Разрядность фиксирована.
4. Даже если это класс, данные хранятся непосредственно в его членах, а указателей он не содержит.
5. Размер байта достаточен для представления sizeof(x)-1.
Нужны версии функции только для типов, удовлетворяющих всем пяти условиям. То есть если кому то взбредёт сократить байт до четырёх бит, то на такой платформе требуется поддерживать уже типы не более 16-ти байт. А при духбитном байте не более 4-х. Платформы с адресацией каждого бита не рассматриваем вообще.

И даже если условие будет изменено, то в моей программе только поменяется тип элементов входного массива с unsigned char на unsigned short, а тебе же твою программу переписать с нуля придётся... И ты после этого о переносимости своего кода заикаешься?

0x100 заменить на 0x10000 - это нифига не переписывать с ноля. И откуда short появится? Любая минимально адресуемая ячейка - это байт.

И так, господа, если число является встроенным типом, у нас есть гарантия, что оно располагается в памяти непрерывно.

Ни кто не гарантировал, что тип встроенный.

bool ContainsConsecutiveValues(const unsigned char arrNumbers[]

И за каждым вызовом таскать приведение типа (пусть и без фактического преобразования, но в тексте оно должно будет быть), да ещё и передачу sizeof. Это всё таки не библиотечная функция, чтоб так усложнять синтаксис. Ни где не сказано, что число уже разобрано на байты. Оно только с "точки зрения" аппаратуры хранится в байтах, но синтаксически представляет из себя единую сущность - число. И при вызове должно использоваться именно число, а не указатель на его байты.

Код: Выделить всё

bool Test(const int &x)
{
 size_t Counts[sizeof(x)];
 const unsigned char *Digit;
 size_t  *Count;
 for (Count=Counts+sizeof(Order)-1; Count>=Counts; --Count)
 {
  (*Count)=0;
 }
 for (Digit=(const uunsigned char*)Order+sizeof(Order)-1; Digit>=(const unsigned char*)Order; --Digit)
 {
  if (Digit<sizeof(Order))
  {
   Count=Counts+Digit;
   ++(*Count);
   if ((*Count)!=1)
   {
    return false;
   }
  }
  else
  {
   return false;
  }
 }
 for (Count=Counts+sizeof(x)-1; Count>=Counts; --Count)
 {
  if ((*Count)!=1)
  {
   return false;
  }
 }
 return true;
}

вызывающая функция:

Код: Выделить всё

int x;
HANDLE File;
DWORD Readen;
File=CreateFile(FileName.c_str(), GENERIC_READ, FILE_SHARE_READ, nullptr, OPEN_EXISTING, FILE_ATTRIBUTE_NORMAL, NULL);
 if (File==INVALID_HANDLE_VALUE)
 {
  return false;
 }
 ReadFile(File, (void*)&x, sizeof(x), &Readen, nullptr)
 if (Readen!=sizeof(x))
 {
  CloseHandle(File);
  retrun false;
 }
 if (!Test(x))
 {
  CloseHandle(File);
  retrun false;
 }

. А у Вас как? У Вас

Код: Выделить всё

int x;
HANDLE File;
DWORD Readen;
File=CreateFile(FileName.c_str(), GENERIC_READ, FILE_SHARE_READ, nullptr, OPEN_EXISTING, FILE_ATTRIBUTE_NORMAL, NULL);
 if (File==INVALID_HANDLE_VALUE)
 {
  return false;
 }
 ReadFile(File, (void*)&x, sizeof(x), &Readen, nullptr)
 if (Readen!=sizeof(x))
 {
  CloseHandle(File);
  retrun false;
 }
 if (!ContainsConsecutiveValues((const int*)&x, sizeof(x)))
 {
  CloseHandle(File);
  retrun false;
 }

.

Сионист, вот скажи, зачем ты создаёшь подобные темы, в которых спрашиваешь совета, как лучше делать, затем критикуешь предлагаемые решения,

Ну как где я хоть словом критикую решение? Я лишь указываю на то, что Вы пытаетесь решить другую задачу. Задача: дано число, требуется проверить, что получится, если разобрать его на байты. Не разобрать, а проверить, что получилось бы, если разобрать. Решено: дан массив, требуется проверить его элементы.

Вообще-то у меня будет вот так:

Код: Выделить всё

 if (!ContainsConsecutiveValues(x))
 {
  CloseHandle(File);
  retrun false;
 }

Я ведь специально написал перегрузки. Последний пост просматривал?

И даже если бы перегрузок не было, то это глупо придираться к отличному общему решению только потому, что оно более сложно вызывается, в то время как твоё решение вызывается проще только потому, что оно узкое и заточено всего под один тип. Сделать перегрузку в общем решении - это самое простое, что можно сделать, чтобы побить твой просто смешной аргумент.

На счёт задачи для числа частей большего, чем 255 - мы просто по разному подправили в уме условия задачи. Одно из условий ведь в любом случае нужно поправить, иначе задача становится не просто не решаемой, а противоречивой. Я логично предположил, что части превращаются из байт в слова, и бить исходное число уже нужно будет на слова, которые смогут дать значения от 0 до 65535. И именно отсюда у меня появился unsigned short. Ты же убрал условие уникальности значений, что в принципе поменяло задачу. Я думал, что это условие вообще ключевое и нерушимое. Собственно всегда так и получается. Я пытаюсь логически мыслить, но каждый раз ты меня удивляешь...

1. А ни кто не говорил, что в каждой версии программы должно быть более одной версии функции.
2. Оболочечные функции на ровном месте - не есть хорошо. Их назначение - исправлять синтаксис вызова в тех случаях, когда переделка целевой функции трудоёмка. Не более того. А здесь и так разработка функции с ноля. Но

Код: Выделить всё

bool ContainsConsecutiveValues(unsigned long n)
{
  return ContainsConsecutiveValues((const unsigned char*)&n, sizeof(n));
}

- именно оболочечная. Чем это плохо? Элементарно: сначала в стек помещается значение n и адрес возврата в вызывающую функцию и вызывается сама оболочечная функция, потом указатель на эту копию n, значение sizeof(n) и адрес возврата в оболочечную функцию и вызывается целевая функция, потом целевая функция выполняется, чистит стек, возвращает управление, оболочечная функция ещё раз чистит стек и возвращает управление. Вместо этого можно один раз вызвать целевую функцию, положив в стек или значение n и адрес возврата, или указатель на n и адрес возврата, при её исполнении скопировать указатель на n в локальную переменную на стеке и сложить адреса с константой, полученной из sizeof(n) на этапе компиляции, после исполнения вернуть управление. Убирается: один вызов из двух, один возврат из двух, запись sizeof(n) в стек и доступ к нему, запись в стек и чтение оттуда одного из двух вариантов информации о n: или значения, или указателя. Итог чуть быстрей и тратит чуть меньше памяти. Конечно можно предположить, что компилятор оптимизирует оболочечную функцию до инлайна, но:
1. Даже в этом случае sizeof(n) всё ещё будет гоняться через стек, так как до шаблонизации целевой функции компилятор не догадается, то есть получится нечто среднее.
2. Зачем это вообще делать, когда можно сделать и проще и лучше?

Я логично предположил, что части превращаются из байт в слова, и бить исходное число уже нужно будет на слова, которые смогут дать значения от 0 до 65535. И именно отсюда у меня появился unsigned short. Ты же убрал условие уникальности значений, что в принципе поменяло задачу.

Нет. Я не убираю условие, иначе задача вообще отменяется. Байт может состоять и из 16-ти, и из 48-ми и даже из 96-ти бит. Байт - единица памяти, а не информации. Любая минимально адресуемая ячейка двоичной памяти называется байтом за исключением платформ с адресацией каждого бита. Ну ещё на сетуне не было байтов из-за того, что там память вообще не была двоичной. У той машины вместо байтов были трайты. Но сетунь поддерживать не надо. Если байт состоит из 16-ти бит, то можно записать в байт 65536 разных чисел от 0 до 65536 и пятому условию соответствует sizeof до 65536 и поддерживать требуется какой то один тип с sizeof<256, но тогда более жёстким становится первое условие, чем пятое. А если байт меньше 8-ми бит, то более жёстким будет пятое условие, чем первое и, например, при четырёхбитном байте придётся уже поддерживать тип с sizeof<16, это уже не может быть даже uint64_t, так как 32/4 уже равно 16. А самвеа вообще предложил заменить один костыль двумя.
1. Сначала убрать submit с формы и вызывать его скриптом на скриптоджаве и через явное невидимое поле передавать имя кнопки.
2. Потом читать имя из значения поля и разбирать его средствами скрипта на php.
Разбор имени скриптом остаётся, у меня он уже был в том костыльном решении, которое я и просил улучшить. При этом его придётся писать через те же циклы. Вместо этого я нашёл решение гораздо лучше: добавить в имя пару скобок и разобрать его средствами языка php. На скриптоджаве писать не надо, всё полностью на php, писать разбор не надо, достаточно вызвать готовую функцию key, проверяется на isset только та часть имени, которая совпадает у всех кнопок данного назначения. А у других кнопок назначение другое и там всё равно условие пишется ради выполнения/не выполнения других действий, а значит и другого текста в фигурных скобках. А ради этого пишется естественно другое условие.

Developing.ru

Разбить число на байты и проверить их последовательность

Re: Как лучше решить подзадачу?

Re: Как лучше решить подзадачу?

Re: Как лучше решить подзадачу?

Re: Как лучше решить подзадачу?

Re: Как лучше решить подзадачу?

Re: Как лучше решить подзадачу?

Re: Разбить число на байты и проверить их последовательность

Re: Как лучше решить подзадачу?

Re: Как лучше решить подзадачу?

Re: Разбить число на байты и проверить их последовательность