Цикл от 0 до n без ветвления

@hi_vsem · Регистрация: 14.11.2018

Студворк — интернет-сервис помощи студентам

Есть цикл while(true), counter = 0, additive - шаг и THRESHOLD - положительное число :

C++
1
2
3
4
while(true){
If(counter < THRESHOLD
counter+=additive;
}

Как можно заменить if внутри while, чтобы убрать ветвление, но чтоб код делал тоже самое?

C++
1
2
3
while(true){
...
}

Я пробовал такой способ, но логическое сравнение в машинном коде это тоже ветвление

C++
1
2
3
while(true){
counter += (counter < TRESHOLD)*additive;
}

@hi_vsem · 10.10.2023, 16:44 **[ТС]**

Хорошо, возможно не прав, с CMOV не сталкивался. Но он лично у меня в коде в qt creator 4.11.1 и не появляется, вместо него cmpl jb

@DrOffset · 10.10.2023, 16:54

hi_vsem, он появляется в режиме release. Но это уже второй вопрос.

Откуда ноги растут у задачи? Зачем нужно здесь избегать сравнения и ветвления? Это не для x86 делается? Для какой-то платформы, где очень дорогой branching? Поясните.

@hi_vsem · 10.10.2023, 17:03 **[ТС]**

Архитектура в этой конкретной задаче не указывается, но в других это х86. Это одна из задач на развитие для программирования плат и схем, где важно сократить нагрузку любыми способами. Эта задача именно о том чтоб сделать код линейным.

@gunslinger · 10.10.2023, 21:29

А если как-то так (если я правильно понял суть задачи)?

C++
1
counter += (THRESHOLD / additive + (THRESHOLD % additive)) * additive;

@Evgen173 · 10.10.2023, 21:47

gunslinger, THRESHOLD не меняется, additive не меняется, выражение после += не обнулится, а значит counter будет увеличиваться с каждым разом

@gunslinger · 10.10.2023, 21:58

Зачем обнулять? И я привел весь код - while, if и прочие for не нужны.
Также можно заменить += на =, раз counter изначально равен 0. Но в "общем" случае лучше использовать +=.

Алексей1153 · 11.10.2023, 01:53

Сообщение от hi_vsem

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

сильно подозреваю, что компилятор в релизе сумеет простые случаи оптимизировать, даже если там будет if или короткий switch

Алексей1153 · 11.10.2023, 02:09

@hi_vsem · 11.10.2023, 08:23 **[ТС]**

Как сказали выше, такой вариант будет просто вечно увеличиваться, так и шаг будет не равен additive

Verevkin · 11.10.2023, 08:25

Сообщение от hi_vsem

Эта задача именно о том чтоб сделать код линейным.

Объясни, вот где тут ветвление?

Команда cmp модифицирует флаги (ZF, например), это не переход.

@Volga_ · 11.10.2023, 08:30

hi_vsem, можно ли так:

C++
1
2
while(true) { break; }
counter=THRESHOLD*additive;

???

@hi_vsem · 11.10.2023, 08:36 **[ТС]**

А смысл? Надо внутри while(true) увеличивать counter на значение additive, пока он не станет больше или равен THRESHOLD. Потом каждый виток цикла counter не будет меняться

Алексей1153 · 11.10.2023, 08:39

Сообщение от hi_vsem

Как сказали выше, такой вариант будет просто вечно увеличиваться, так и шаг будет не равен additive

хм, а что мешает убрать цикл и шаг сделать равным additive?

@hi_vsem · 11.10.2023, 09:07 **[ТС]**

Эм, то что с этим кодом так не будет работать?)

@KSergey9 · 11.10.2023, 09:16

Знаю я такие "задачки".
Когда станет известен на них ответ - то внезапно выяснится одно из двух (да, я не умею "без ветвлений"):
1) либо ответ уже был дан, но он по каким-то формальным признакам на совпадает с "ответом правильным"
2) либо в "правильном ответе" ветвление таки будет, однако задающий вопрос с хитрым прищуром скажет "это совсем не то, потому что..." (далее любой набор слов, убеждающий задающего вопрос). На любые уточнение "так это же...!" будет простой ответ "ты не понимаешь, иди учись мальчик".
3) вполне себе вариант "решения у задачи нет, мы тебя проверяли"

А суть задач проста: они не про "развитие", они про унизить салагу с хитрым прищуром, чтобы не задавался. Всё.
Никакого другого реального смысла в них нет.

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

@hi_vsem · 11.10.2023, 09:29 **[ТС]**

Скорее всего так и будет, ибо вариант с

C++ (Qt)
1
counter+=(counter<THRESHOLD)*additive;

забраковали сразу, ещё до того как я этот вопрос задал здесь, хотя формально ветвления нет

Verevkin · 11.10.2023, 09:41

Сообщение от hi_vsem

забраковали сразу

Почему забраковали-то?

@hi_vsem · 11.10.2023, 10:13 **[ТС]**

Посчитали что этот код не линейный. Надо линейный, чтоб в две строчки, внутри while(true) и решение как-то связанно с тем, что числа со знаком хранятся в дополнительном коде.

@повар1 · 11.10.2023, 10:15

C++
1
2
while(true)
   while((counter+=additive)<THRESHOLD);

Verevkin · 11.10.2023, 10:29

Сообщение от hi_vsem

Посчитали что этот код не линейный.

Почему он нелинейный-то? Какие критерии нелинейности?!
Писец какой-то...

Сообщение от hi_vsem

решение как-то связанно с тем, что числа со знаком хранятся в дополнительном коде.

Ладно, хрен с тобой!
Вот тебе решение для маньяков-чикатилов. А я пошёл в HALO гонять, надоел ты мне, извращенец. Я тебя боюсь. Страшно, когда такие люди среди нас бродят в толпе: с виду нормальные, а могут и БРИТОВКОЙ ПО ГОРЛЫШКУ!

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
using namespace std;
 
#define ADDITIVE  1
#define SHIFT     (8 * sizeof(unsigned) - 1)
 
int foo(const int threshold)
{
  unsigned counter = 0;
 
  do
  {
    counter += (~(threshold - counter - 1) >> SHIFT) * ADDITIVE;
    printf("# counter: %d\n", counter);
  } while (true);
 
  return counter;
}
 
int main()
{
  return foo(4);
}

Новые блоги и статьи Все статьи Все блоги /
Программный домашний кинотеатр russiannick 27.09.2026 Сподобился на программный домашний кинотеатр. В качестве ЯВУ по традиции выбрал js. В помощники взял Яндекс-Алису. Было создано три зала на разные интересы. исторические и ретро сериал Хичкок. . .	Беседа с ИИ о программистах, недопускающих к созданию и правке кода генеративные ИИ и причины этого zorxor 21.09.2026 Раньше я радовался или получал некоторые эмоции, пусть небольшие, но всё же, от самого процесса написания кода, рекомпиляции и запуска, видя постепенное развитие программы и прочее. А теперь лень. . .	Мобильное приложение ColorStep pavlinmavlin 17.09.2026 Реализовал приложение Красный, Зеленый, Синий в Unity3d + c#. Название изменил на ColorStep. Приложение прошло модерацию и теперь доступно для скачивания. Делал его сам, шаг за шагом — и вот,. . .	Запрет дублирования строк в табличной части Maks 13.09.2026 Реализация из решения ниже выполнена на нетиповом справочнике "Нормы ТО" с табличной часть "Виды ТО", разработанного в КА2, со следующими реквизитами: - ВидТО (СправочникСсылка. ВидыТО); - ВидГСМ. . .
Скрипты Tampermonkey для CyberForum, ChatGPT, Claude и пр. Jin X 06.09.2026 Скрипты Tampermonkey для CyberForum, ChatGPT, Claude и пр. Работая с форумом и нейросетями в браузере часто хочется что-то подкорректировать или добавить какого-то функционала. Ниже прикреплён. . .	Программа опроса у.з. расходомера SLS-720F Argus19 02.09.2026 Программа опроса у. з. расходомера SLS-720F Программа опрашивает один раз в минуту три ультразвуковых расходомера SLS-720F через интерфейс RS-485 по протоколу Modbus RTU. Опрашиваются регистры. . .	Hyper-V: Компьютер должен поддерживать доверенный платформенный модуль 2.0. Maks 31.08.2026 При установке Windows 11 на виртуальную машину Hyper-V 2-го поколения вылезла такая ошибка: Решение: в параметрах виртуальной машины, в разделе "Безопасность" (Security) активировать флаг. . .	Архитектура биовида Стива в Майнкрафте: Зачем бонобо кубический каннибализм anaschu 30.08.2026 Кубический Вагинокапитализм в Minecraft: Математический инвариант ОДУ и рок Стивов-бонобо Главная задача разработанной «Модели Всего» — наглядно продемонстрировать наличие системной «судьбы». . .

@hi_vsem 0 / 0 / 0 Регистрация: 14.11.2018 Сообщений: 135
	10.10.2023, 16:44 [ТС]
	Хорошо, возможно не прав, с CMOV не сталкивался. Но он лично у меня в коде в qt creator 4.11.1 и не появляется, вместо него cmpl jb 0

@DrOffset 19506 / 10109 / 2464 Регистрация: 30.01.2014 Сообщений: 17,834
	10.10.2023, 16:54
	hi_vsem, он появляется в режиме release. Но это уже второй вопрос. Откуда ноги растут у задачи? Зачем нужно здесь избегать сравнения и ветвления? Это не для x86 делается? Для какой-то платформы, где очень дорогой branching? Поясните. 0

@hi_vsem 0 / 0 / 0 Регистрация: 14.11.2018 Сообщений: 135
	10.10.2023, 17:03 [ТС]
	Архитектура в этой конкретной задаче не указывается, но в других это х86. Это одна из задач на развитие для программирования плат и схем, где важно сократить нагрузку любыми способами. Эта задача именно о том чтоб сделать код линейным. 0

@Evgen173 И тут вот те нате 322 / 209 / 117 Регистрация: 12.07.2016 Сообщений: 555
	10.10.2023, 21:47
	gunslinger, THRESHOLD не меняется, additive не меняется, выражение после += не обнулится, а значит counter будет увеличиваться с каждым разом 0

@gunslinger place status here 3192 / 2227 / 640 Регистрация: 20.07.2013 Сообщений: 6,028
	10.10.2023, 21:58
	Зачем обнулять? И я привел весь код - while, if и прочие for не нужны. Также можно заменить += на =, раз counter изначально равен 0. Но в "общем" случае лучше использовать +=. 0

Алексей1153 фрилансер 6504 / 5749 / 1134 Регистрация: 11.10.2019 Сообщений: 15,394
	11.10.2023, 02:09
	0

@hi_vsem 0 / 0 / 0 Регистрация: 14.11.2018 Сообщений: 135
	11.10.2023, 08:23 [ТС]
	Как сказали выше, такой вариант будет просто вечно увеличиваться, так и шаг будет не равен additive 0

@hi_vsem 0 / 0 / 0 Регистрация: 14.11.2018 Сообщений: 135
	11.10.2023, 08:36 [ТС]
	А смысл? Надо внутри while(true) увеличивать counter на значение additive, пока он не станет больше или равен THRESHOLD. Потом каждый виток цикла counter не будет меняться 0

@hi_vsem 0 / 0 / 0 Регистрация: 14.11.2018 Сообщений: 135
	11.10.2023, 09:07 [ТС]
	Эм, то что с этим кодом так не будет работать?) 0

@KSergey9 631 / 526 / 104 Регистрация: 05.08.2022 Сообщений: 2,810
	11.10.2023, 09:16
	Знаю я такие "задачки". Когда станет известен на них ответ - то внезапно выяснится одно из двух (да, я не умею "без ветвлений"): 1) либо ответ уже был дан, но он по каким-то формальным признакам на совпадает с "ответом правильным" 2) либо в "правильном ответе" ветвление таки будет, однако задающий вопрос с хитрым прищуром скажет "это совсем не то, потому что..." (далее любой набор слов, убеждающий задающего вопрос). На любые уточнение "так это же...!" будет простой ответ "ты не понимаешь, иди учись мальчик". 3) вполне себе вариант "решения у задачи нет, мы тебя проверяли" А суть задач проста: они не про "развитие", они про унизить салагу с хитрым прищуром, чтобы не задавался. Всё. Никакого другого реального смысла в них нет. PS Справедливости ради изредка в самом деле показывают хитрые трюки. Однако цель всё равно такая, как я озвучил. 0

@hi_vsem 0 / 0 / 0 Регистрация: 14.11.2018 Сообщений: 135
	11.10.2023, 10:13 [ТС]
	Посчитали что этот код не линейный. Надо линейный, чтоб в две строчки, внутри while(true) и решение как-то связанно с тем, что числа со знаком хранятся в дополнительном коде. 0